Để tìm tất cả chuỗi con lặp lại trong một chuỗi đã cho

Question

Tôi lặp lại câu hỏi phỏng vấn: Để tìm tất cả chuỗi con lặp lại trong chuỗi đã cho với kích thước tối thiểu là 2. Thuật toán phải hiệu quả.

Mã cho câu hỏi trên được đưa ra bên dưới nhưng không hiệu quả.

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <set> 
#include <string> 

using namespace std; 

int main() 
{ 
    typedef string::const_iterator iterator; 
    string s("ABCFABHYIFAB"); 
    set<string> found; 

    if (2 < s.size()) 
     for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i) 
      for (iterator x = s.begin(); x != i; ++x) 
      { 
       iterator tmp = mismatch(i, j, x).second;; 
       if (tmp - x > 1) 
        found.insert(string(x, tmp)); 
      } 

      copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n")); 
} 

Câu hỏi của tôi là, có cấu trúc dữ liệu nào có thể thực hiện câu hỏi trên trong thời gian độ phức tạp của O (N)?

Nếu câu trả lời của bạn là cây Suffix hoặc Hashing hãy giải thích nó.

Answer 1

Nếu bạn phân tích đầu ra cho chuỗi "AAAAAAAAAAAAAA", sau đó có O (n ²) nhân vật trong nó, vì vậy các thuật toán tối thiểu là O (n ²).

Để đạt được O (n²), chỉ cần xây dựng suffix tree cho mỗi hậu tố của s (chỉ mục [1.n], [2..n], [3..n], ..., [n. .n]). Nó không quan trọng nếu một trong các chuỗi không có nút kết thúc riêng, chỉ cần đếm tần suất mỗi nút được sử dụng.

Cuối cùng, lặp qua mỗi nút có số> 1 và in đường dẫn của nó.

Answer 2

Đó chỉ là một ý tưởng hoang dã, nhưng đáng thử (tuy nhiên, nó tiêu thụ bộ nhớ O (N), trong đó N là độ dài của chuỗi chính). Thuật toán không phải là O (N), nhưng có lẽ nó có thể được tối ưu hóa.

Ý tưởng là, bạn không muốn so sánh chuỗi thường xuyên. Bạn có thể thu thập giá trị băm của dữ liệu đã đọc (ví dụ: tổng số mã ASCII của các ký tự đã đọc) và so sánh các băm. Nếu băm bằng nhau, các chuỗi có thể là bằng nhau (nó phải được kiểm tra sau). Ví dụ:

ABCAB 

A -> (65) 
B -> (131, 66) 
C -> (198, 133, 67) 
A -> (263, 198, 132, 65) 
B -> (329, 264, 198, 131, 66) 

Vì bạn chỉ quan tâm đến 2+ giá trị độ dài, bạn phải bỏ qua giá trị cuối cùng (vì nó luôn tương ứng với một ký tự).

Chúng tôi thấy hai giá trị bằng nhau: 131 và 198. 131 là viết tắt của AB và cho biết cặp, tuy nhiên 198 là viết tắt của ABC và BCA, mà phải bị từ chối bằng kiểm tra thủ công.

Đó chỉ là ý tưởng chứ không phải chính giải pháp. Hàm băm có thể được mở rộng để tính toán vị trí của ký tự trong chuỗi con (hoặc cấu trúc chuỗi). Phương pháp lưu trữ giá trị băm có thể được thay đổi để cải thiện hiệu suất (tuy nhiên trong chi phí sử dụng bộ nhớ tăng).

Hope tôi đã giúp chỉ là một chút :)

Answer 3

Tôi không biết làm thế nào cây hậu tố có thể nhận được tất cả các chuỗi lặp lại, chuỗi "mississippi" xây dựng cây hậu tố như thế này:

xin lỗi, tôi nhìn thấy. "Cuối cùng, lặp qua mỗi nút với số> 1 và in đường dẫn của nó." "đếm" là số lượng nút con này

tree-->|---mississippi    m..mississippi 
     | 
     |---i-->|---ssi-->|---ssippi i .. ississippi 
     |  |   | 
     |  |   |---ppi  issip,issipp,issippi 
     |  | 
     |  |---ppi    ip, ipp, ippi 
     | 
     |---s-->|---si-->|---ssippi s .. ssissippi 
     |  |  | 
     |  |  |---ppi  ssip, ssipp, ssippi 
     |  | 
     |  |---i-->|---ssippi  si .. sissippi 
     |    | 
     |    |---ppi  sip, sipp, sippi 
     | 
     |---p-->|---pi     p, pp, ppi 
       | 
       |---i     p, pi 

--- Suffix Tree for "mississippi" --- 

Answer 4

Tôi nghĩ rằng sự cố này cũng có thể được giải quyết bằng cách sử dụng lập trình động.