Задача №114740. Двойной палиндром
Ваня работает на заводе по изготовлению палиндромов. На заводе есть заготовка — строка \(s\) длины \(n\), состоящая из строчных букв английского алфавита, из которой Ваня может вырезать любую подстроку на продажу. Напомним, что палиндром — строка, читающаяся одинаковым образом как слева направо, так и справа налево.
Обычные палиндромы всем надоели и их никто не покупает, поэтому он решил производить двойные палиндромы. Двойной палиндром — это строка, которая является конкатенацией двух палиндромов равной длины. Например, строки « aabb », « aaaa » являются двойными палиндромами, а строки « abba » и « aaaabb » нет.
Ваня задался вопросом, сколько существует способов вырезать из строки \(s\) двойной палиндром, а именно, сколько существует пар \((l, r)\), что подстрока \(s_l s_{l+1} \ldots s_r\) является двойным палиндромом. Помогите Ване найти ответ на этот важный вопрос!
В первой строке задано целое число \(n\) (\(1 \leq n \leq 500\,000\)) — длина строки \(s\). Во второй строке задана строка \(s\), состоящая из строчных букв английского алфавита.
Выведите единственное число — искомое число подстрок, которые являются двойными палиндромами.
В первом примере двойными палиндромами являются 5 подстрок длины 2 (« ab », « ba », « ac », « ca » и « ac »), а так же вся строка (« abacac »).
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | \(n\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 19 | \(n \leq 500\) | |
| 2 | 33 | \(n \leq 5000\) | |
| 3 | 48 | – |
6 abacac
6
5 aaaaa
6