Найти наименьший период входной строки в O (n)?

Учитывая следующую проблему:

Определение:

Пусть S строка над алфавитом Σ.S' самый маленький периодS еслиS' самая маленькая строка такая, что:

S = (S')^k (S'')

гдеS'' это префиксS, Если нет такогоS' существует, тоS не является периодическим.

Пример :S = abcabcabcabca, затемabcabc это период сS = abcabc abcabc a, но самый маленький периодabc поскольку .S = abc abc abc abc a

Дайте алгоритм, чтобы найти наименьший период входной строкиS или объявить, чтоS не является периодическим.

Подсказка: вы можете сделать это вO(n) ...

Мое решение: мы используем KMP, который работает в O (n).

По определению задачи S = (S ') ^ k (S ''), то я думаю, что если мы создадим автоматы за кратчайший период и найдем способ найти этот кратчайший период, то я 'м сделано.

Проблема в том, где поставить стрелку FAIL автомата ...

Благодарим за любую идею ,

С уважением

Ответы на вопрос(3)

Ваш ответ на вопрос