在大文本中查找回文

Question

所以我们得到了一个60万字符的文本，没有空格和句号。我已经把这些从课文中删除了。现在我要找到所有长度大于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

注意，如果字符串s₀…s_n是回文，那么s₁…s_n-1也是回文

简言之，遍历文件，搜索每个长度为7和8的有效回文（感谢@tobias\u 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])