Python3.x - 使用字典计算所有子字符串的出现次数

Question

给定一些字符串 S，此代码将计算字符串 S 所有可能子串的出现次数。

#count[i]=no of different substrings in the string that occurs exactly i times
count=[0]*(100001)
a=input()
dic={}
n=len(a)
for i in range(n):
    temp=""
    for j in range(i,n,1):
        temp+=a[j]
        if temp in dic:
            dic[temp]+=1
        else:
            dic[temp]=1
for k,v in dic.items():
    count[v]+=1

例如，对于字符串 "ababa"，数组将为：

cnt[1]=4 {"ababa", "abab", "baba", "bab"} 正好出现一次
cnt[2]=4 {"aba", "ab", "ba", "b"} 恰好出现两次
cnt[3]=1 {"a"} 正好出现三次
cnt[4]=0
cnt[5]=0

我有兴趣了解我的代码的运行时间

Answer 1

基本上有两部分代码需要分别考虑：

构建 `dic` 的嵌套循环。
构建 `count` 的循环。

对于 1. 有两个循环需要考虑。 i 循环将运行 n 次，j 循环将每次运行 n-i 次。

这意味着 j 循环将第一次运行 n 次，第二次 n-1 次，依此类推，直到运行s 一次 i = n-1。因此这个块的总运行ning时间是n(n+1)/2，也就是O(n^2).

（注意：我假设字典访问需要固定时间，大多数情况下都是如此）。

对于 2. 只需要考虑一个循环，它将运行存在多次唯一子串。对于长度为 n 的字符串，唯一子字符串的最大数量也是 n(n+1)/2，这也是 O(n^2).

所以，运行宁时间是O(n^2)。对于 n = 10e5，操作次数为 ~10e10，这将花费大约 10 秒，使用标准假设 10e9 操作需要 1 秒。

Python3.x - 使用字典计算所有子字符串的出现次数

Python3.x - counting occurences of all substrings using dictionaries

substring

python-3.x