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

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

Пусть 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 автомата ...

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

С уважением