在Python中计算字符串s中不同的子串数量的程序

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

因此，如果输入是s =“abaa”，那么输出将是8，因为子串是[“a”，“b”，“ab”，“ba”，“aa”，“aba”，“baa”，“abaa”]。

要解决此问题，我们将按照以下步骤进行 –

trie：一个新映射
n：s的大小
对于i从0到n-1的范围，执行以下操作
- curr：trie
- 对于j从i到n-1的范围，执行以下操作
  - c：s [j]
  - 如果c不在curr中，则
  - curr [c]：一个新映射
  - curr：curr [c]
  - curr [“*”]：真
q：制造队列，并插入trie
ans：0
当q不为空时，执行以下操作
- ans：ans + 1
- t：q的左侧项，并从q中删除此项
- 对于t中的每个c，执行以下操作
  - 如果c与“*”不同，则
  - 在q的末尾插入t [c]
返回ans-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))