如何用trie（或后缀trie）生成所有回文子串？

Question

给定一个字符串"ababacba"，如何生成所有可能的回文子串？

我正在考虑以下方法：

用原始字符串生成后缀trie
反转字符串
生成反转字符串的所有后缀
对于每个后缀，通过后缀 trie 中的每个节点进行比较以确定回文

然而，这似乎对某些情况不起作用，例如它检测到 baba 为回文，而实际上不是，因为读取 ababacba 是与阅读 ababacba 相同，两个粗体语句都有 abab 及其相反的 baba。

因此，我认为这种方法是无效的，那么如何使用 trie 生成所有回文子串呢？

字符串 ababacba 的期望输出：

ababa
bab
aba

谢谢。

Answer 1

首先找出所有的子串，然后检查它们是否是回文。对于很长的字符串，此方法可能不会那么快。

def substrings(string, n):
    result = []
    for i in range(len(string)-n+1):
        result.append(string[i:i+n])
    return result

def all_substrings(string, min_n=2):
    result = []
    for n in range(min_n, len(string)):
        result+=substrings(string, n)
    return result


def is_palindrom(string):
    return string == string[::-1] #[::-1] reverses string (look for slicing)

def sub_palindroms(string, min_n=2):
    return [s for s in all_substrings(string, min_n=min_n) if is_palindrom(s)]

print(sub_palindroms('ababacba'))

如何用trie（或后缀trie）生成所有回文子串？

How to generate all palindrome substrings with trie (or suffix trie)?

algorithm

suffix-tree

palindrome

trie

data-structures