একটি স্ট্রিং s দেওয়া আছে। s-র সকল ভিন্ন নন-এমপটি উপস্ট্রিং (substring) এর সংখ্যা বের করতে হবে।
সমস্যা উদাহরণ
ইনপুট: s = "abaa"
আউটপুট: 8
ব্যাখ্যা: উপস্ট্রিংগুলো: ["a", "b", "ab", "ba", "aa", "aba", "baa", "abaa"]
সমাধানের পদ্ধতি (Trie + BFS)
- একটি Trie (প্রিফিক্স ট্রি) তৈরি করুন নেস্টেড ডিকশনারি দিয়ে
- প্রতিটি স্ট্রাটিং ইনডেক্স i থেকে শেষ পর্যন্ত সব সাবস্ট্রিং Trie-তে ইন্সার্ট করুন
- প্রতিটি নোডে
"*"কী দিয়ে শেষ চিহ্নিত করুন - BFS দিয়ে Trie-এর সব নোড গণনা করুন (রুট বাদ দিয়ে)
পাইথন কোড
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
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 # রুট বাদ দিন
s = "abaa"
print(solve(s)) # আউটপুট: 8টেস্ট কেস
ইনপুট: "abaa"
আউটপুট: 8
সময় জটিলতা: O(n²) - সব সাবস্ট্রিং প্রসেস করা হয়।
স্থান জটিলতা: O(n²) - Trie সংরক্ষণ।
