Python中计算s中不同子串个数的程序

假设我们有一个字符串 s，我们必须找到 s 的不同非空子串的数量。

因此，如果输入类似于 s = "abaa"，那么输出将是 8，因为子字符串是 ["a", "b", "ab", "ba", "aa", "aba", "咩”，“啊”]。

示例

让我们看看以下实现以获得更好的理解 -

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