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