Python प्रोग्राम - स्ट्रिंग में विशिष्ट सबस्ट्रिंग की संख्या गिनें

एक स्ट्रिंग s दी गई है, हमें s के विशिष्ट गैर-खाली सबस्ट्रिंग की संख्या खोजनी है।

उदाहरण

इनपुट: s = "abaa"

आउटपुट: 8

व्याख्या: सबस्ट्रिंग हैं ["a", "b", "ab", "ba", "aa", "aba", "baa", "abaa"]।

एल्गोरिदम (ट्राई/प्रीफिक्स ट्री)

1. trie := {} (खाली डिक्शनरी)
2. n := len(s)
3. i 0 से n-1 तक:
   • curr := trie
   • j i से n-1 तक:
     • c := s[j]
     • यदि c curr में नहीं: curr[c] := {}
     • curr := curr[c]
     • curr["*"] := True (अंत मार्कर)
4. q := deque([trie])
5. ans := 0
6. जब q खाली नहीं:
   • ans += 1
   • t := q.popleft()
   • प्रत्येक c in t के लिए:
     • यदि c != "*": q.append(t[c])
7. ans - 1 लौटाएं (रूट नोड घटाएं)

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

इनपुट/आउटपुट

Input: "abaa"
Output: 8