给定一些字符串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”，数组将为：
我对了解我的代码的运行时间很感兴趣
您的代码本质上有两个部分需要分别考虑：
对于1.，有两个循环需要考虑。i循环将运行n时间，j循环将n-i每次运行时间。
这意味着j循环将n第一次运行，n-1第二次运行，依此类推，直到当when运行一次i = n-1。因此，该块的总运行时间为n（n + 1）/ 2，即O（n ^ 2）。
（注意：我假设字典访问在大多数情况下都是固定时间的）。
对于2。只有一个循环可以考虑，该循环将运行唯一的子字符串多次。对于长度为n的字符串，唯一子字符串的最大数量再次为n（n + 1）/ 2，也为O（n ^ 2）。
因此，运行时间为O（n ^ 2）。对于n = 10e5，操作数约为10e10，使用标准假设10e9操作需要1秒，这大约需要10秒。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句