একটি স্ট্রিং s (দৈর্ঘ্য n) এবং কোয়েরি লিস্ট Q দেওয়া আছে। Q[i] = (l, r)। প্রতিটি কোয়েরির জন্য s[l..r]-এ কতগুলো ডISTINCT সাবস্ট্রিং আছে সেটি বের করুন।
উদাহরণ
s = "pptpp", Q = [(1,1),(1,4),(1,1),(0,2)] → আউটপুট: [1, 8, 1, 5]
এলগরিদম (Suffix Array + LCP / Kasai Algorithm)
kasai(s, suff, n)ফাংশন দিয়ে LCP অ্যারে বানান।- প্রতিটি কোয়েরির জন্য:
sub := s[l:r+1]- সাফিক্স অ্যারে বানান এবং সর্ট করুন।
kasaiদিয়ে LCP বের করুন।- ডISTINCT সাবস্ট্রিং =
Σ(len(suffix[i]) - lcp[i-1])
পাইথন কোড
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)) # আউটপুট: [1, 8, 1, 5]
ইনপুট / আউটপুট
"pptpp", [(1,1),(1,4),(1,1),(0,2)] [1, 8, 1, 5]
