Chương trình Python đếm số xâu con khác nhau trong chuỗi

Cho chuỗi s, đếm số xâu con (substring) không rỗng và khác nhau.

Ví dụ

Input: s = "abaa"

Output: 8

Các xâu con: "a", "b", "ab", "ba", "aa", "aba", "baa", "abaa".

Thuật toán (Trie / Cây tiền tố)

1. Xây dựng Trie từ tất cả hậu tố của s:
   • Với mỗi vị trí bắt đầu i, thêm các ký tự s[i:] vào Trie.
   • Đánh dấu nút kết thúc bằng khóa đặc biệt '*'.
2. BFS/DFS duyệt Trie, đếm số nút (trừ gốc) → chính là số xâu con khác nhau.

Mã nguồn Python

from collections import deque

def solve(s):
    trie = {}
    n = len(s)
    for i in range(n):
        curr = trie
        for j in range(i, n):
            c = s[j]
            if c not in curr:
                curr[c] = {}
            curr = curr[c]
            curr["*"] = True  # đánh dấu kết thúc từ

    q = deque([trie])
    ans = 0
    while q:
        ans += 1
        t = q.popleft()
        for c in t:
            if c != "*":
                q.append(t[c])

    return ans - 1  # trừ nút gốc

# Test
s = "abaa"
print(solve(s))  # Output: 8

Độ phức tạp

• Thời gian: O(n²) — xây dựng Trie từ tất cả hậu tố.
• Không gian: O(n²) worst case (chuỗi toàn ký tự khác nhau).

Lưu ý: Có thể dùng Suffix Array + LCP hoặc Suffix Automaton để đạt O(n), nhưng Trie đủ đơn giản cho bài toán này.