Строка \(s\) назывется префиксом строки \(t\), если строка \(t\) начинается со строки \(s\). Строка \(s\) назывется суффиксом строки \(t\), если строка \(t\) заканчивается на строку \(s\).

Назовём две строки \(s\) и \(t\) циклически эквивалентными, если существует циклический сдвиг, переводящий строку \(s\) в строку \(t\); другими словами строки \(s\) и \(t\) циклически эквивалентны тогда и только тогда, когда, строка \(s\) может быть получена из строки \(t\) путем перемещения некого суффикса строки \(t\) в начало строки \(t\). Например, строки \(ababba\) и \(abbaab\) циклически эквивалентны, в то время как строки \(ababba\) и \(ababab\) нет. В частности, любая строка циклически эквивалентна самой себе.

Дана строка \(t\) длины \(n\). Требуется найти такой префикс \(p\) и такой суффикс \(s\) строки \(t\), что:

• \(p\) циклически эквивалентен \(s\) (и, как следствие, их длины равны)
• длина \(p\) не превосходит \(\frac{n}{2}\) (то есть \(p\) и \(s\) не пересекаются в \(t\))
• длина \(p\) максимальна