在大文中找到回文

Question

所以我们得到了一个大约600000个字符的文本，没有“空格”和完整停止。我从文本中删除了那些。现在我必须在那篇文章中找到长度大于7的所有回文，我需要一些帮助来解决这个问题。

我已经尝试了一件事，但那太慢了。

from string import ascii_letters, digits

s = open("pg1150.txt").read()
s = s.lower()
s = "".join([c for c in s if c in ascii_letters or c in digits])
for i in range(len(s)):
    for j in range(i + 6, len(s) + 1):
        t = s[i:j]
        if t == t[::-1]: 
            print(t)

输入文本是：http://www.gutenberg.org/cache/epub/1150/pg1150.txt

Answer 1

注意如果一个字符串s0 ... sn是一个回文，那么s1 ... sn-1也是一个回文

简而言之，遍历您的文件，搜索长度为7和长度为8的每个有效回文（感谢@tobias_k，否则您只会获得奇数回文），但不是打印它，而是将其索引保存到单独的列表中。

for i in range(len(s) - 8):
    t1 = s[i:i+7]
    t2 = s[i:i+8]

    if t1 == t1[::-1]: 
        index_table.append(i)
    if t2 == t2[::-1]: 
        index_table.append(i)

#You have to ensure that the only substring of length 7 that goes unchecked isn't a palindrome
if s[-7:] == s[-7:][::-1]:
    index_table.append(len(s) - 7)

现在您拥有了所有未来回文的“基础”，使用前面提到的递归关系很容易构建所有其他回文。

for i in index_table:
    n = 0
    while (s[i-n] == s[i+6+n]):
        print(s[i-n:i+6+n])