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

Question

Given a string "ababacba", how can I generate all possible palindrome substrings?

I was thinking of an approach of the following:

1. Generate a suffix trie with the original string
2. Reverse the string
3. Generate all suffixes of the reversed string
4. For each of this suffixes, compare by going each node in the suffix trie to determine palindrome

However, it seems that this might not work for certain cases such as it detects baba as a palindrome when it is not, because reading ababacba is the same as reading ababacba, both bolded statement have abab and its reversed baba.

Hence, I think this approach is not valid, so how can I generate all palindrome substrings using a trie?

Desired output for string ababacba :

ababa
bab
aba

Thank you.

Answer 1

First find all substrings and then check if they are palindrome. This methods probably doesn't work that fast for very long strings.

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'))