Znajdź najmniejszy okres ciągu wejściowego w O (n)?

Question

Biorąc pod uwagę następujący problem:

Definicja:

Niech S będzie ciągiem nad alfabetem Ď. S' jest najmniejszy okres S jeśli S' jest najmniejszym ciąg taki, że:

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

gdzie S'' jest prefiksem S. Jeśli nie istnieje taka S', to S jest nie okresowa.

Przykład: S = abcabcabcabca. Następnie abcabc jest okresem od S = abcabc abcabc a, ale najmniejszy okres to abc od S = abc abc abc abc a.

Podaj algorytm, aby znaleźć najmniejszy okres ciągu wejściowego S lub zadeklaruj, że S nie jest okresowy.

Podpowiedź: Można to zrobić w O(n) ...

Moje rozwiązanie: Używamy KMP, która biegnie w O (n).

Definiując problem, S = (S ')^k (S "), to myślę, że jeśli stworzymy automatów na najkrótszy czas i znajdziemy sposób na znalezienie najkrótszego okresu, to już koniec.

Problem polega na tym, gdzie umieścić fail strzałkę z automatów ...

jakieś pomysły będą bardzo mile widziane,

Pozdrowienia

Answer 1

nie jestem pewien, że rozumiem swoją próbę rozwiązania . KMP jest jednak użytecznym podprocedłem - najmniejszy okres to to, jak daleko KMP przesuwa łańcuch igieł (tj. S) po pełnym dopasowaniu.

Answer 2

ten problem można rozwiązać za pomocą funkcji Z, pomocny może być tutorial this.

Answer 3

Sprawdź, czy to rozwiązanie działa dla O (n). Użyłem obrotu ciągów.

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; 

} 

cały program jest dostępny w this github repository