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ć, 142857142857
jest 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łę?
142857
to nie jest najdłuższy, ponieważ142857142857
jest dłuższy. Myślę, że powinieneś edytować pytanie, aby wyjaśnić, co rozumiesz przez „powtarzający się wzór”.Odpowiedzi:
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 p i 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 k ≥ 2 i x jest poprawnym przedrostkiem w . Największy kwadrat zawarty w tym powtórzeniu to(w⌊ k / 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.
źródło