chuỗi dài nhất xuất hiện n lần

Question

Đối với một chuỗi có độ dài L, tôi muốn tìm chuỗi con dài nhất xuất hiện n (n < L) hoặc nhiều lần trong ths chuỗi. Ví dụ, chuỗi con dài nhất xảy ra từ 2 lần trở lên trong "BANANA" là "ANA", một khi bắt đầu từ chỉ mục 1 và một lần nữa bắt đầu từ chỉ mục 3. Các phần tử được phép chồng chéo lên nhau.

Trong chuỗi "FFFFFF", chuỗi dài nhất xuất hiện 3 lần trở lên là "FFFF".

Thuật toán bạo lực cho n = 2 sẽ chọn tất cả các cặp chỉ mục trong chuỗi, sau đó chạy dọc theo cho đến khi các ký tự khác nhau. Phần chạy dọc có O (L) và số cặp là O (L^2) (không cho phép trùng lặp nhưng tôi bỏ qua điều đó) vì vậy độ phức tạp của thuật toán này cho n = 2 sẽ là O (L^3). Đối với các giá trị lớn hơn của n, giá trị này tăng theo cấp số nhân.

Có một thuật toán hiệu quả hơn cho vấn đề này không?

Answer 1

Cây hậu quả giải quyết các loại vấn đề này rất nhanh, thường là thời gian và không gian O (n).

Nhìn vào trang wiki:

Suffix Trees.

và đọc các tài liệu (phần chức năng) trên trang đó mà liên kết đến:

Longest Repeated Substring.

Answer 2

Longest common substring problem