На одной из тренировок школьников на NEERC в этом году, была одна интересная строковая задача. Вот её приблизительное условие:
Строка называется хорошей, если какой либо её префикс ненулевой длины и отличный от всей строки совпадает с её суффиксом. Дана строка длиной до 105 символов, нужно для каждого её циклического сдвига определить является он хорошим или нет.
Условие в оригинале и авторское решение по задаче можно найти где-то-тут. Оригинальное название задачи "Заклинание Границы".
В авторском решении, что-то весьма хитрое с z-функцией и разделяй-и-властвуй, кажется, я не очень понял. Предлагаю пообсуждать решение здесь :).
P.S. Некто e-maxx, говорил, что, вроде бы, подобная задача была когда то в Петрозаводске на Станкевич контесте. И что у нее есть решение как z-функцией, так и суффиксным деревом.
Для каждого сдвига перебираем длину суфикса, который совпадает с префиксом, бинарным поиском. Суфикс и префикс сравниваем за константу полиномиальными хешами.
Если не проходит по времени, увеличиваем таймлимит :о)
Там, кстати, можно обойтись без суффиксных массивов, только "разделяй и влавствуй" + z-функция.
Алгоритм описан в книге Jewels of Stringology на странице 119.
Думается всетаки можно таким методом решить.
Научимся решать: http://olympiads.ru/zaoch/2009/problems/k.shtml .
Я в свое время решал с помощью KMP. Собственно, текст в котором ищем text = s + s, искомый образец patern = s. n = strlen(s). Как обычно построим префикс функцию и начнем искать образец в тексте. Начиная с символа n-1 (индексация с 0) при поиске образца в тексте обращаем внимание на следующий факт.
Если после некоторой итерации указатель на символ в образце равен n, то в случае с задачей поиска строки в подстроке можно говорить о том, что найдено вхождение образца в текст. В нашей же задаче значение указателя -- это и будет наибольший префикс, который является суффиксом. Если p = n, то возьмем значение префикс функции от s.