python - 如何优化此 Python 代码以使其运行得更快？

Question

我正在解决一个有时间和内存限制的问题，不幸的是，这没有达到时间限制。

我是 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

Answer 1

在性能方面更喜欢 xrange，因为它在 python2.X 中迭代速度更快但我能给出的最好建议是使用 timeit在调整算法的同时衡量变化和改进。

用谷歌搜索这里有另一个实现:Longest Common substring解决方案，但 python-Levenshtein图书馆可能是你最好的选择，因为它有速度的 C 扩展......