Python - Tìm độ dài chuỗi con lặp lại dài nhất

Cho chuỗi chữ thường s, tìm độ dài chuỗi con (substring) xuất hiện ít nhất 2 lần. Nếu không có, trả về 0.

Ví dụ

Input: s = "abdgoalputabdtypeabd"
Output: 3
Giải thích: Chuỗi con "abd" xuất hiện 3 lần.

Thuật toán: Mảng hậu tố (Suffix Array) + LCP

1. Tạo danh sách tất cả hậu tố của chuỗi
2. Sắp xếp danh sách hậu tố theo thứ tự từ điển
3. So sánh từng cặp hậu tố liền kề để tìm tiền tố chung dài nhất (LCP)
4. Độ dài LCP lớn nhất chính là kết quả

Mã Python

def lcs(s1, s2):
    """Tìm tiền tố chung dài nhất của 2 chuỗi"""
    n = min(len(s1), len(s2))
    for i in range(n):
        if s1[i] != s2[i]:
            return s1[:i]
    return s1[:n]

def solve(s):
    suffixes = []
    n = len(s)
    max_len = 0
    
    # Tạo tất cả hậu tố
    for i in range(n):
        suffixes.append(s[i:n])
    
    # Sắp xếp
    suffixes.sort()
    
    # So sánh cặp liền kề
    for a, b in zip(suffixes, suffixes[1:]):
        rtr = lcs(a, b)
        if len(rtr) > max_len:
            max_len = len(rtr)
    
    return max_len

# Test
s = "abdgoalputabdtypeabd"
print(solve(s))  # Output: 3

Phân tích độ phức tạp

• Thời gian: O(n² log n) - do sắp xếp n chuỗi dài trung bình n/2
• Không gian: O(n²) - lưu trữ tất cả hậu tố

Cải tiến

Để đạt O(n log n) hoặc O(n), có thể dùng:

• Suffix Array với thuật toán DC3/SA-IS + Kascho algorithm cho LCP
• Suffix Automaton (SAM) - O(n) thời gian và không gian
• Binary Search + Rolling Hash (Rabin-Karp) - O(n log n)

Phương pháp trên phù hợp cho chuỗi ngắn (n < 10⁴). Với chuỗi lớn, nên dùng SAM hoặc Binary Search + Hash.