3622
правки
Изменения
м
→Число подпалиндромов
Рассмотрим очередной шаг алгоритма после добавления символа <tex>x</tex>. Обозначим за <tex>t</tex> вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ.
Заметим, что новые палиндромы, которые добавляет <tex>x</tex> {{---}} это <tex>t'</tex>, а также все палиндромы, достижимые из <tex>t</tex> по суффиксным ссылкам (т.к. только они содержат новую вершину новый символ <tex>x</tex>). Для того чтобы быстро найти их число, будем хранить в каждой вершине длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного <tex>t</tex> по мере добавления новых символов.
