Znajdź najdłuższy powtarzający się wzór w ciągu

Szukam wydajnego algorytmu do znajdowania najdłuższego powtarzającego się wzorca w ciągu.

Weźmy na przykład następujący ciąg liczb:

5431428571428571428571428571427623874534.

Jak widać, 142857142857jest to najdłuższy wzór, który powtarza się kilka razy (przynajmniej dwa razy) w tym ciągu.

Powtarzany ciąg nie powinien zawierać żadnych pomysłów, a nie brutalną siłę?

Problem jest zaskakująco nietrywialny. Najpierw dwa algorytmy brutalnej siły. Kwadrat („powtarzany wzór”) jest podany na podstawie jego długości $\ell$ i pozycja $p$i wymaga czasu $O(\ell)$do weryfikacji. Jeśli przejdziemy wszystko$\ell$ i $p$, otrzymujemy $O(n^3)$algorytm. Możemy to poprawić, najpierw zapętlając$\ell$, a następnie skanowanie ciągu za pomocą dwóch uruchomionych wskaźników w odległości $\ell$. W ten sposób można sprawdzić, czy kwadrat długości$2\ell$ istnieje w czasie liniowym, co daje całkowity czas działania wynoszący $O(n^2)$.

Kolpakov i Kucherov opracowali algorytm znajdowania wszystkich maksymalnych powtórzeń w jednym słowie w czasie$O(n)$ [1], a ich algorytm można wykorzystać do znalezienia wszystkich maksymalnych kwadratów w czasie $O(n)$. Powtórz to podsłowo formie$w^kx$, gdzie $k \geq 2$ i $x$ jest poprawnym przedrostkiem $w$. Największy kwadrat zawarty w tym powtórzeniu to$(w^{\lfloor k/2 \rfloor})^2$. Za pomocą tej formuły podane są wszystkie maksymalne powtórzenia w jednym słowie (których są tylko$O(n)$ wielu), można znaleźć największy plac.

[1] Kolpakov, R., i Kucherov, G. (1999). Znajdowanie maksymalnych powtórzeń w słowie w czasie liniowym . W Foundations of Computer Science, 1999. 40. doroczne sympozjum na temat (s. 596–604). IEEE.