algorithm - 如何用trie(或后缀trie)生成所有回文子串？

Question

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

我正在考虑以下方法:

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

但是，这似乎在某些情况下可能不起作用，例如它检测到 baba 为回文，而实际上它不是，因为读取 ababacba 与读一个babacba，两个粗体语句都有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'))