Количество отдельных палиндромных подстрок

Учитывая строку, я знаю, как найти количество палиндромных подстрок в линейном времени с использованием алгоритма Манахера. Но теперь мне нужно найти число отдельных/уникальных подстрок палиндромических. Теперь это может привести к алгоритму O (n + n^2) - одному «n» для нахождения всех таких подстрок, а n^2 для сравнения каждой из этих подстрок с уже найденными, чтобы проверить, является ли он уникальным.Количество отдельных палиндромных подстрок

Уверен, что существует алгоритм с лучшей сложностью. Я думал о том, что, возможно, попробую удачу с деревьями суффиксов? Есть ли алгоритм с лучшей временной сложностью?

источник

2013-12-09 Liam Willis

Не сравнивает ли каждый элемент с каждым другим элементом n²? Поэтому я думаю, что это будет O (n + n²) = O (n²). Тем не менее, я согласен, но все же неплохо. – CompuChip

@CompuChip Да, мой плохой. Отредактировал его. –

Я бы просто положил подстроки, которые вы нашли в хеш-таблице, чтобы не допустить одновременного проведения одинаковых результатов.

Время доступа к хеш-таблице - O (1).

источник

2013-12-09 14:52:49 zavg

Я знаю, как найти _number_ таких подстрок в линейном времени, а не подстроках. В основном я говорю об алгоритме Манахера. –

@LiamWillis: Wikipedia http://en.wikipedia.org/wiki/Longest_palindromic_substring не упоминает * число *, но явно заявляет: * Однако, как отмечалось, например, Apostolico, Breslauer & Galil (1995), тот же алгоритм может также можно использовать для поиска всех максимальных палиндромных подстрок где угодно внутри входной строки, снова в линейном времени. * Примечание слова ** find **, используемое в этом предложении. Я смущен. –

В том же алгоритме Манахера, когда вы найдете подстроки вокруг центра, просто сохраните его в хеш-таблице, как это было предложено @zavg. –

Количество отдельных палиндромных подстрок

ответ

Смежные вопросы