โปรแกรมนับจำนวน substring ที่แตกต่างกันในสตริงด้วย Python

คำอธิบายปัญหา

กำหนดสตริง s หาจำนวน **substring ที่ไม่ซ้ำกัน** (distinct non-empty substrings)

ตัวอย่าง

s = "abaa" → Output: 8

Substrings: "a", "b", "ab", "ba", "aa", "aba", "baa", "abaa"

ขั้นตอนการแก้ปัญหา (Trie)

1. สร้าง Trie: ใส่ทุก suffix s[i:] ลง Trie
2. นับโหนดทั้งหมดใน Trie (ยกเว้น root) = จำนวน distinct substrings
3. ใช้ BFS/queue นับโหนด

การตนการทำงาน (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  # mark end
    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  # exclude root

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

อินพุต / เอาต์พุต

Input:  "abaa"
Output: 8