Đề xuất thuật toán chuỗi để tìm tất cả tiền tố chung của danh sách các chuỗi

Question

Thuật toán nào bạn đề xuất để tìm ra các tiền tố phổ biến nhất dài nhất trong danh sách chuỗi?

tôi có thể có chuỗi như:

Call Mike and schedule meeting. 
Call Lisa 
Call Adam and ask for quote. 
Implement new class for iPhone project 
Implement new class for Rails controller 
Buy groceries 

Tôi muốn tìm hiểu các tiền tố sau:

"Call " 
"Implement new class " 

tôi sẽ sử dụng Objective C, do đó, một giải pháp sẵn sàng cacao làm sẽ là một cộng (mặc dù không phải là một).

Answer 1

Điều đó phụ thuộc vào những gì bạn sẵn sàng xem xét tiền tố.

Tôi cho rằng câu trả lời chung là tạo Trie (có thể là cây hậu tố hậu tố) lưu trữ tất cả các chuỗi vào một cây n-ary. Xem http://en.wikipedia.org/wiki/Trie

Tùy thuộc vào tiêu chí của bạn cho 'prefix' (nói, n ký tự), bạn có thể chọn tất cả các nút của bậc n rằng có nhiều hơn một trẻ em.

Bạn sẽ có danh sách các tiền tố lặp lại.

Answer 2

Bạn có thể chèn tất cả các chuỗi của mình vào một số trie (còn gọi là cây tiền tố). Sau đó đi qua các trie từ gốc cho đến khi bạn tìm thấy một nút với nhiều hơn một đứa trẻ (hoặc chỉ dừng lại chèn chuỗi khi bạn sẽ phải nối thêm một đứa con thứ hai vào một nút).

Answer 3

Edit: cho câu hỏi làm rõ:

1. Sắp xếp các dây
2. Tìm tiền tố chung dài nhất của mỗi cặp liền kề
3. Sắp xếp và dedupe các tiền tố thông thường, sau đó loại bỏ bất kỳ đó là một tiền tố khắt khe của khác.

Thực tế, bước (3) chỉ yêu cầu bạn xóa bất kỳ khoản tiền nào là tiền tố/tiền tố của tài khoản khác, mà bạn có thể thực hiện bằng trie hoặc bất kỳ thứ gì thay vì sắp xếp. Trong thực tế, có thể toàn bộ điều có thể được thực hiện nhanh hơn với một trie được chú thích phù hợp - nếu bạn bao gồm "đếm" tại mỗi nút thì bạn đang tìm kiếm chính xác các nút có số lượng 2+, không có con đếm 2+.

Nhưng sắp xếp được tích hợp và khi bạn đã sắp xếp, bạn có thể phát hiện tiền tố bằng cách xem các mục lân cận, vì vậy có thể ít nỗ lực hơn.

[Câu trả lời gốc:

Chỉ một thao tác một lần, tìm tiền tố chung dài nhất giữa tất cả các chuỗi?

Tôi có thể làm điều đó theo độ dài của tiền tố. Trong pseudo-code, và giả sử chuỗi nul-chấm dứt:

prefixlen = strlen(first_string); 
foreach string in the list { 
    for (i = 0; i < prefixlen; ++i) { 
     if (string[i] != first_string[i]) { 
      prefixlen = i; 
      break; 
     } 
    } 
    if (prefixlen == 0) break; 
} 

common_prefix = substring(firststring, 0, prefixlen); 

]

Answer 4

1. Chèn tất cả các chuỗi thành một cấu trúc dữ liệu Trie.
2. DFS từ gốc để tìm nút đầu tiên có nhiều hơn 1 cạnh đi ra khỏi nó.
3. đường dẫn từ gốc đến nút được tính toán trong bước 2 cung cấp tiền tố chung dài nhất cho tất cả tập hợp các chuỗi.