Найдите самый длинный префикс строки s, который является подстрокой обращения строки s

Question

Есть ли способы использовать алгоритм линейного времени, чтобы найти самый длинный префикс строки s, который является подстрокой обращения строки s?

Answer 1

Да, есть решение O(n) с деревом суффиксов . Предположим, n - это длина строки s.

1. Вычисление srev, обращение строки s, равно O(n) (и на самом деле это может быть O(1), но это не имеет значения).
2. Дерево суффиксов для srev может быть построено за O(n) времени.
3. Самый длинный префикс s в srev можно найти в O(n) времени, используя дерево суффиксов.

Answer 2

Примените алгоритм Кнута-Морриса-Пратта для поиска заданной строки (S) в перевернутой строке (T).На каждой итерации он находит самый длинный префикс S, который является суффиксом T [1..i].Тогда вам просто нужно найти максимальную длину этих префиксов.