计算文本文件中长度≥ 7 的所有回文子串

Question

编写一个程序，给定一个长字符串（比如 1.000.000 个字符），计算所有长度 ≥ 7 的回文子串，即正向和反向拼写相同的子串。您可以使用以下代码将完整文本从文件读取为字符串，将其转换为小写，并删除除字母和数字以外的所有内容。文件 saxo.txt 是 http://www.gutenberg.org/cache/epub/1150/pg1150.txt

的本地副本

from string import ascii_letters, digits

s = open("The Danish History.txt").read()
s = s.lower()
s = "".join([c for c in s if c in ascii_letters or c in digits])

def isPalindrome(str):
    def isPal(str):
        if len(str) >= 7:
            return True
        else:
            str[0] == str[-1] and isPal(str[1:-1])

    return isPal(s)


print(isPalindrome(s))

我得到了这个练习，我必须计算一个文本文件的所有长度 ≥ 7 的回文子串。我已经使用上面的代码来证明我的 string/textfile 是一个回文。我不知道我现在必须做什么来计算长度 ≥ 7 的所有回文子串的列表。

提前致谢。

Answer 1

只要单词的长度大于或等于 7，无论它是否为回文，您的函数都会 return True。您可以检查字符串的反转版本是否与原始字符串相同：string[::-1] == string 就足够了。

在我看来，“回文子串”并不意味着回文单词。在这种情况下，您可能希望遍历所有 子字符串 ，而不仅仅是被空格分隔的单词。可能有更有效的方法来做到这一点，但以下是我的建议：

from string import ascii_letters, digits

with open('The Danish History.txt', 'r') as f:
    s = f.read()

s = s.lower()
s = "".join([c for c in s if c in ascii_letters or c in digits])

palins = []
for length in range(7, len(s) + 1): # loop over possible lengths
    for start in range(len(s) - length): # loop over starting positions
        substring = s[start:start+length]
        if substring[::-1] == substring: # if palindromic
            palins.append(substring)

计算文本文件中长度≥ 7 的所有回文子串

Compute all palindromic substrings of length ≥ 7 of a textfile

python

function

list

palindrome