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

Question

Учитывая следующую задачу:

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

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

Любые идеи, было бы весьма признателен,

С уважением

Answer 1

Я не уверен, что я понимаю вашу попытку решения , KMP - полезная подпрограмма, хотя - наименьший период - это то, как KMP перемещает игольную строку (т. Е. S) после полного совпадения.

Answer 2

эта проблема может быть решена с использованием функции Z, this учебник может вам помочь.

Answer 3

Посмотрите, подходит ли это решение для O (n). Я использовал поворот строк.

public static int stringPeriod(String s){ 

    String s1= s; 
    String s2= s1; 

    for (int i=1; i <s1.length();i++){ 
     s2=rotate(s2); 
     if(s1.equals(s2)){ 
      return i; 
     } 
    } 

    return -1; 
} 

public static String rotate(String s1){ 

    String rotS= s1; 

    rotS = s1.substring(1)+s1.substring(0,1); 

    return rotS; 

} 

Полная программа доступна в this github repository