我正在解决一个有时间和内存限制的问题,不幸的是,这没有达到时间限制。
我是 Python 的新手,因此欢迎任何有关更快/更好方法的反馈。
这是程序试图解决的问题:
将两个字符串 A 和 B 的相似度定义为它们共享的最长公共(public)前缀的长度。即AAAB和AABCAAAB的相似度为2。
程序应输出输入字符串及其所有后缀的相似度总和。即对于 AAAB,它应该输出
相似度(AAAB,AAAB) + 相似度(AAAB,AAB) + 相似度(AAAB,AB) +相似度(AAAB,B) = 4 + 2 + 1 + 0 = 7
input第一行是要输入的字符串个数,后面每一行都是一个要处理的字符串。
from array import array
n = int(sys.stdin.readline())
A = [0] * n #List of answers
for i in range(1,n+1):
string = sys.stdin.readline().strip()
A[i-1] = len(string)
for j in range(1, len(string)):
substr = string[j:len(string)]
sum = 0
for k in range(0, len(substr)):
if substr[k] != string[k]:
break
else:
sum += 1
A[i-1] += sum
for i,d in enumerate(A):
print d
最佳答案
在性能方面更喜欢 xrange,因为它在 python2.X 中迭代速度更快但我能给出的最好建议是使用 timeit在调整算法的同时衡量变化和改进。
用谷歌搜索这里有另一个实现:Longest Common substring解决方案,但 python-Levenshtein图书馆可能是你最好的选择,因为它有速度的 C 扩展......
关于python - 如何优化此 Python 代码以使其运行得更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8740257/