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

9

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łę?

Juho
źródło
3
Nie zdefiniowałeś, co oznacza „kilka razy”, ale jeśli „dwa razy” liczy się jako „kilka razy”, 142857to nie jest najdłuższy, ponieważ 142857142857jest dłuższy. Myślę, że powinieneś edytować pytanie, aby wyjaśnić, co rozumiesz przez „powtarzający się wzór”.
Tsuyoshi Ito,
bardzo dobry punkt. Zaktualizuję pytanie.
8
Czy potrzebujesz, aby występowanie wzorca było od siebie niezależne? Ponieważ jeśli nie, 142857142857 nadal nie jest najdłuższym powtórzeniem; 142857142857142857142 występuje dwukrotnie. W każdym razie zwykłą odpowiedzią na takie pytania są „drzewa przyrostków”.

Odpowiedzi:

15

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

Kolpakov i Kucherov opracowali algorytm znajdowania wszystkich maksymalnych powtórzeń w jednym słowie w czasieO(n) [1], a ich algorytm można wykorzystać do znalezienia wszystkich maksymalnych kwadratów w czasie O(n). Powtórz to podsłowo formiewkx, gdzie k2) i x jest poprawnym przedrostkiem w. Największy kwadrat zawarty w tym powtórzeniu to(wk/2))2). Za pomocą tej formuły podane są wszystkie maksymalne powtórzenia w jednym słowie (których są tylkoO(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.

Yuval Filmus
źródło