পাইথনে s-এ স্বতন্ত্র সাবস্ট্রিংয়ের সংখ্যা গণনা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের s-এর স্বতন্ত্র অ-খালি সাবস্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="abaa" এর মতো হয়, তাহলে আউটপুট হবে 8 কারণ, সাবস্ট্রিংগুলি হল ["a", "b", "ab", "ba", "aa", "aba", " baa", "abaa"]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• trie :=একটি নতুন মানচিত্র
• n :=s এর আকার
• আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
  • curr :=trie
  i থেকে n - 1 রেঞ্জে j-এর জন্য
  • করুন
    • c :=s[j]
    • যদি c curr-এ না থাকে, তাহলে
      • curr[c] :=একটি নতুন মানচিত্র
    • curr :=curr[c]
    • curr["*"] :=সত্য
• q :=একটি সারি তৈরি করুন এবং ট্রাই সন্নিবেশ করুন
• উত্তর :=0
• যখন q অ-খালি, do
  • উত্তর :=উত্তর + ১
  • t :=q এর বাম আইটেম, এবং q থেকে এই আইটেমটি মুছে দিন
  টি-তে প্রতিটি c-এর জন্য
  • করুন
    • যদি c "*" এর মত না হয়, তাহলে
      • q এর শেষে t[c] ঢোকান
• উত্তর ফেরত দিন - 1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))

ইনপুট

"abaa"

আউটপুট

8