Podany ciąg s, znajdź najkrótszy ciąg t, taki, że t^m = s.Podany ciąg s, znajdź najkrótszy ciąg t, taki, że, t^m = s
Przykłady:
s="aabbb" => t="aabbb"
s="abab" => t = "ab"
Jak szybko można to zrobić?
Oczywiście naiwnie, dla każdego m dzieli | s |, mogę spróbować, jeśli podciąg (s, 0, | s |/m)^m = s.
Można znaleźć rozwiązanie w czasie O (d (| s |) n), gdzie d (x) jest liczbą dzielników s. Czy można to zrobić bardziej efektywnie?
To jest problem z obliczaniem okresu łańcucha. Knuth, Morris and Pratt's sequential string matching algorithm to dobre miejsce na rozpoczęcie. Jest to artykuł zatytułowany "Fast Pattern Matching in Strings" z 1977 roku.
Jeśli chcesz się z tym ubrać, sprawdź artykuł "Znalezienie wszystkich okresów i początkowych palindrom struny równoległej" przez Breslauer i Galil w 1991 roku z ich streszczenie:
optymalny o (log log n) algorytm CRCW-PRAM czasu do obliczania wszystkich okresy ciągiem są prezentowane. Poprzednie algorytmy równoległe obliczają okres tylko wtedy, gdy jest krótszy niż połowa długości ciągu znaków . Algorytm ten może być użyty do znalezienia wszystkich początkowych palindromów z ciągu znaków w tym samym czasie i granicach procesora. Oba algorytmy są możliwie najszybsze nad ogólnym alfabetem. Otrzymujemy niższą granicę dla znalezienia palindromów przez modyfikację wcześniej znanego niższego związanego do znalezienia okresu ciągu [3]. Kiedy dostępne są procesory p , granice stają się \ Theta (d n p e + log log d1 + p = ne 2p).
modyfikacja Boyer-Moore mógłby obsłużyć to w O (n), gdzie n oznacza długość s
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
Tak można to zrobić w O(|s|) czasie.
Możesz wyszukać ciąg "docelowy" o długości n w ciągu "źródłowym" o długości m w czasie O(n+m). W oparciu o to zbuduj rozwiązanie.
Niech zarówno źródłowy i docelowy być s. Dodatkowym ograniczeniem jest to, że 1 i dowolne pozycje w źródle, które nie dzielą |s|, nie są prawidłowymi pozycjami wyjściowymi dla meczu. Oczywiście wyszukiwanie samo w sobie zawsze kończy się niepowodzeniem. Ale jeśli jest częściowe dopasowanie i osiągnąłeś koniec łańcucha z kwasem, to masz rozwiązanie pierwotnego problemu.
Bardzo podoba mi się ta rzecz nazwie Z-algorytm: http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
Dla każdej pozycji oblicza najdłuższy podciąg wychodząc stamtąd, który jest również przedrostek całego łańcucha. (oczywiście w czasie liniowym).
a a b c a a b x a a a z
1 0 0 3 1 0 0 2 2 1 0
Biorąc pod uwagę ten „Z-table” łatwo jest znaleźć wszystkie ciągi, które mogą być potęgowania do całej sprawy. Po prostu sprawdź wszystkie pozycje, jeśli pos+z[pos] = n.
W naszym przypadku:
a b a b
0 2 0
Tutaj pos = 2 daje 2+z[2] = 4 = n stąd najkrótsza ciąg można użyć jest jeden o długości 2.
To będzie nawet pozwalają znaleźć przypadki, gdzie tylko przedrostek z potęgowania meczów strunowych, takich jak:
a b c a
0 0 1
Tutaj (abc)^2 można wyciąć z oryginałem strunowy. Ale oczywiście, jeśli nie chcesz takich meczów, przejdź tylko do dzielników.