Хм, лекция по структуре данных, данная в Петрозаводске, это не то же самое, что архив сборов, так? К тому же не факт, что такая же информация будет доступна в Ижевске.

Разве не разумнее было бы написать подобное замечание в ЛС автору — чтобы он отредактировал тему или спрятал ее в черновики? Вместо того, чтобы становиться соучастником:)

В целом ведь хорошая тема, если бы не упоминание о ПЗ/Ижевске. Тогда получилось бы так — кто прочел и разобрался, тот молодец; кто не прочел — сам виноват.

It's here

И участники сборов в Птз никак не могли об этом прочитать, а участники сборов в Ижевске могут прочитать. Это нехорошо.

Предположим, что на сборы в Ижевске поедут какие-нибудь не самые сильные команды из УрФУ, участники которых не участвовали в подготовке УрФУ-контеста — соответственно, они будут писать этот контест. Однако, они вполне могли слышать про Ваше дерево палиндромов. А теперь предположим, что ADJA не создал никакого поста.

И в первом случае одни участники не знали о структуре, а другие знали, и во втором случае одни участники не знали о структуре, а другие знали. Но есть один нюанс...

По поводу сборов в Ижевске тут другой вариант — автор знал о существовании сборов, не знал дат (хотя их, конечно же, можно было узнать), но совершенно забыл об этих сборах на протяжении последних пары недель точно.

Единственная проблема сейчас, насколько я думаю, лишь в том, что сборы в Птз и Ижевске теперь возможно нельзя будет со 100% точностью сравнивать. В целом, остальные доступные алгоритмы тоже читали не абсолютно все команды, и ссылок принудительно не давали. Тут разница наверное в том, что на возможную связь дерева палиндромов и сборов заострили внимание в комментариях.

Название структуры на palindromic tree обязательно изменю, как доберусь до нормального компьютера.

Еще раз сорри, если нарушил какие-то планы или негативно на что-то повлиял.

I think , it is guaranteed O(n) , cause left side of 't' is always pointing to a index less than or equal to the index being added (x) & its always increasing , so it will need at most n iteration .

well, I didn't try to understand your proof. One easy way to prove it:

See on the all of palindromes that ends on position i, all except largest of them appeared before (because they are also prefixes of the largest one). So adding 1 letter adds at most one new palindrome.

This part tries to tell U every time we add a letter, the number of new palindrome may increase by one or not.

It's easy to understand since xAx is the largest suffix palindrome and if there was a new palindrome it must be ended with the letter we added now. And since xAx is the largest suffix palindrome, this new palindrome's left bound will be in the range of xAx. But if a substring Bx is a palindrome, and the left bound of B is less than xAx, we know xB'(B' is the reverse of B) is also a palindrome, and it appears in the left part of xAx, and not ended with right x. So it has appeared. So xAx is the only substring which may be a new palindrome.

We can. But I don't know any way to calculate it easier or faster than in Manacher's algo. The most obvious way is bin search + check if [l..r] is a palindrome. .