Рекомендация: используйте палиндромное дерево (Eertree) — структура, специально заточенная под все различные палиндромные подстроки, строится онлайн за линейное время и возвращает уникальные палиндромы и их вхождения.
Кратко — идея и алгоритм:
- Инициализируйте два корня: фиктивный палиндром длины $-1$ и пустой палиндром длины $0$. Последний добавленный узел — `last`.
- Для каждого символа $s[i]$ (проход слева направо) ищите по суффикс-ссылкам от `last` самый длинный палиндром, который можно расширить символом $s[i]$. Это делается за амортизированное постоянное время.
- Если по переходу символа $s[i]$ узла не существует — создайте новый узел с длиной $len=prev.len+2$, запишите первую позицию (end index) и установите суффикс-ссылку нового узла как следующий подходящий палиндром (по аналогии с суффиксными ссылками).
- Увеличьте счётчик вхождений для текущего узла и назначьте `last` = этот узел.
- После прохода для корректных счётчиков распространите значения вхождений по суффикс-ссылкам (в порядке убывания длины).
Что хранится в узле:
- $len$ — длина палиндрома;
- ссылки-переходы по символам (map или массив для алфавита);
- суффикс-ссылка на наибольший собственный палиндром-суффикс;
- firstPos (конечная позиция первого вхождения) или count вхождений.
Как получить сами подстроки: для каждого узла (кроме двух корней) получить подстроку $s[firstPos-len+1..firstPos]$. Количество уникальных палиндромов равно числу узлов минус два.
Сложность:
- Время построения: амортизированно $O(n)$ (при использовании хеш-таблиц или массивных переходов по фиксированному алфавиту).
- Память: $O(n)$ узлов и переходов (число различных палиндромов в строке не превосходит $n$, плюс два корня).
- Выдача/печать всех уникальных палиндромов — дополнительно $O(P\cdot L_{avg})$ по выводу, где $P$ — число уникальных палиндромов ( $P\le n$ ), $L_{avg}$ — средняя длина при форматированном выводе; извлечение каждой подстроки по индексам — константное при ссылке на исходную строку.
Оптимизации и структуры данных:
- Для небольшого фиксированного алфавита используйте статический массив переходов (прямой индекс) для узла — уменьшает константы и гарантирует $O(1)$ доступ.
- Для большого/произвольного алфавита — unordered_map/dictionary на символ → узел; можно также применять compressing (coordinate-compression) символов.
- Предварительно резервируйте память под вектор узлов, чтобы избежать частых аллокаций.
- Храните firstPos, чтобы извлекать подстроки O(1) по ссылке на исходную строку, не копируя данные.
- Если нужна только подсчёт всех (не обязательно уникальных) палиндромных подстрок — можно использовать Manacher за $O(n)$ (но он не даёт набор уникальных без дополнительной структуры).
- Альтернативы: Manacher + хеширование подстрок для выделения уникальных — даёт корректность, но в худшем случае требует $O(n^2)$ вставок/проверок; суффиксные структуры (suffix automaton/array) можно применять, но они сложнее и медленнее по константам для специально палиндромной задачи.
Вывод: палиндромное дерево (Eertree) — простое, линейное в времени и памяти решение для нахождения всех уникальных палиндромных подстрок и подсчёта их вхождений.