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

Definicja:

Niech S będzie ciągiem znaków nad alfabetem Σ.S' jest najmniejszym okresemS JeśliS' to najmniejszy ciąg taki, że:

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

gdzieS'' to przedrostekS. Jeśli nie, toS' istnieje więcS nie jest okresowy.

Przykład:S = abcabcabcabca. Następnieabcabc to okres odS = abcabc abcabc a, ale najmniejszy okres toabc odS = abc abc abc abc a.

Podaj algorytm, aby znaleźć najmniejszy okres ciągu wejściowegoS lub zadeklaruj toS nie jest okresowy.

Podpowiedź: Możesz to zrobić wO(n) ...

Moje rozwiązanie: Używamy KMP, który działa w O (n).

Definiując problem, S = (S ') ^ k (S' '), myślę, że jeśli stworzymy automaty na najkrótszy okres i znajdziemy sposób na znalezienie najkrótszego okresu, to skończę .

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

Wszelkie pomysły byłyby bardzo mile widziane,

pozdrowienia