Как сгенерировать все подстроки палиндрома с помощью trie (или trie суффикса)?

Question

Учитывая строку "ababacba", как я могу сгенерировать все возможные подстроки палиндрома?

Я думал о следующем подходе:

1. Создание суффиксного дерева с исходной строкой
2. Обратная строка
3. Создание всехсуффиксы перевернутой строки
4. Для каждого из этих суффиксов сравните, перейдя каждый узел в три суффикса, чтобы определить палиндром

Однако, в некоторых случаях это может не сработатьтакой как он обнаруживает baba как палиндром, когда это не так, потому что чтение abab acba такое же, как чтение baba cba, оба выражения, выделенные жирным шрифтом, имеют 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'))