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

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

我对Python相当陌生，因此希望您对更快/更好的方法有任何反馈。

这是程序要解决的问题：

将两个字符串A和B的相似性定义为它们共享的最长公共前缀的长度。即AAAB和AABCAAAB的相似度为2。

程序应输出输入字符串与其所有后缀的相似度之和。即对于AAAB，它应该输出

相似度（AAAB，AAAB）+相似度（AAAB，AAB）+相似度（AAAB，AB）+相似度（AAAB，B）= 4 + 2 +1 + 0 = 7

输入的第一行是要输入的字符串数，随后的每一行都包含要处理的字符串。

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扩展以提高速度...

aaab

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