Задача №112916. Prefixsuffix
В этой задаче мы рассматриваем строки, состоящие из маленьких латинских букв. Фрагмент строки, начинающийся в начале строки, называется ее префиксом. Фрагмент, заканчивающийся в конце строки, называется ее суффиксом. В частности, пустая строка является и префиксом, и суффиксом любой строки.
Две строки называются циклически эквивалентными, если одна из них может быть получена из другой перенесением суффикса из конца в начало строки. Например, строки ababba и abbaab циклически эквивалентны, а ababba и ababab — нет. В частности, строка циклически эквивалентна сама себе.
Дана строка t , состоящая из n букв. Мы ищем ее префикс p и суффикс s одинаковой длины такие, что
- p и s циклически эквивалентны.
- Длина строк p и s не превышает n / 2 (т.е. префикс p и суффикс s не пересекаются в t ).
- Длина p и s максимальна.
Первая строка входного файла содержит одно целое число n ( 1 ≤ n ≤ 1000000 ) — длина строки t . Вторая строка входного файла содержит саму строку t , состоящую из n строчных букв латинского алфавита.
В группе тестов на 30% баллов n ≤ 500 .
В группе тестов на 50% баллов n ≤ 5000 .
Выведите одно число — максимальную длину строк p и s .
15 ababbabababbaab
6