Найти наименьший период входной строки в 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 автомата ...
Благодарим за любую идею ,
С уважением