Нахождение палиндромов в большом тексте

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

Обратите внимание, что если строка s ₀ ... s _n является палиндромом, то s ₁ ... s _n-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])