ให้สตริง s และ Queries Q[i]=(l,r) หาจำนวน Distinct Substrings ใน s[l:r+1] สำหรับแต่ละ Query
ตัวอย่าง: s="pptpp", Q=[(1,1),(1,4),(1,1),(0,2)] → [1,8,1,5]
ขั้นตอน (Suffix Array + LCP per Query)
- ต่อ Query: ดึง Substring
sub - สร้าง Suffix Array ของ
sub - คำนวณ LCP Array ด้วย Kasai Algorithm
Distinct = n(n+1)/2 - sum(LCP)
ตัวอย่างโค้ด
def kasai(s, suff, n):
lcp = [0] * n
inv = [0] * n
for i in range(n):
inv[suff[i]] = i
k = 0
for i in range(n):
if inv[i] == n-1:
k = 0
continue
j = suff[inv[i] + 1]
while i + k < n and j + k < n and s[i+k] == s[j+k]:
k += 1
lcp[inv[i]] = k
if k > 0:
k -= 1
return lcp
def solve(s, Q):
res = []
for left, right in Q:
sub = s[left:right+1]
length = right - left + 1
suffix = [[i, sub[i:]] for i in range(length)]
suffix.sort(key=lambda x: x[1])
suff, suffix = [list(t) for t in zip(*suffix)]
lcp = kasai(sub, suff, length)
count = len(suffix[0])
for i in range(length-1):
count += len(suffix[i+1]) - lcp[i]
res.append(count)
return res
s = "pptpp"
Q = [(1,1),(1,4),(1,1),(0,2)]
print(solve(s, Q)) # Output: [1, 8, 1, 5]อินพุต
"pptpp", [(1,1),(1,4),(1,1),(0,2)]
เอาต์พุต
[1, 8, 1, 5]
