Algorytm KMR, czyli Karpa-Millera-Rosenberga.
Problem 1
Mamy słowo, np. ababcaab. Bierzemy wszystkie podsłowa ustalonej długości np. 3 – czyli będą to aba, bab, abc, itd. Chcemy je posortować leksykograficznie, dobrze by było też wykryć identyczne podsłowa.
Sortujemy podsłowa o długości 1 i o długości 2. Teraz chcemy zamienić te 2 na 4. Są dwie implementacje różniące się właśnie sposobem tej zamiany.
Idea jest generalnie taka: mamy już posortowane podsłowa o długości 2. Do każdego podsłowa dopiszmy to, które jest obok, czyli będziemy mieć pary. Teraz będziemy sortować te pary. Można to zrobić na 2 sposoby:
1. wolniejszy - napisać odpowiednią funkcję porównującą i zapuścić STL-owego sorta – to będzie O(n log²n.)
2. szybszy - sortowanie przez zliczanie względem drugiego elementu a potem [koniecznie stabilne] pierwszego, bo pierwszy jest ważniejszy. Najlepiej wykorzystać tutaj sortowanie pozycyjne. Jeśli użyjemy radix sorta to będzie O (n log n)
Na razie nie podejmuję się rozwinięcia tego, bo moje notatki są dosyć chaotyczne i muszę je rozszyfrować ;)
Problem 2
Mamy tekst złożony z liczb i interesuje nas ile jest identycznych. Chcemy znaleźć tak możliwie małą długość podsłowa, żeby wszystkie były różne [najkrótsze podsłowo takie, że żadna podsłowo się nie powtarza], np. w słowie ababa wystarczy długość 4, a w abcde wystarczy długość 1. Co się powtarza będzie można odczytać z tablicy. Będziemy patrzeć od góry na potęgi 2.
Przykład:
Cały tekst ma długość 100. Bierzemy potęgi 2 czyli w tym przypadku największa możliwa to będzie 64, patrzmy czy coś się powtarza – jeśli tak to musimy wziąć dłuższy fragment. Dopisujemy 32 i mamy teraz słowo o długości 96. Znowu patrzymy, czy się powtarza. Dopisujemy 16 albo zmniejszamy [może być za mało, jeśli się powtórzy], jeśli nie powtórzy, to znaczy, że jest za dużo. Dostaniemy w końcu największe podsłowo dla którego jeszcze się powtarza, czyli szukane przez nas jest o 1 dłuższe – bo oczywiście wtedy się już nie powtarza.
Pseudokod:
I faza: // robimy KMR dla wszystkich potęg 2 mniejszych od n
ZróbKMR (r,s -> r+s) //r,s – długości podsłów
ZróbKMR (1,1 -> 2)
ZróbKMR (2,2 -> 4)
ZróbKMR (2^k, 2^k -> 2^k+1>n) // wykonuj aż będzie większe od n
II faza:
w=0; // w – największa długość, przy której podsłowa się powtarzają
for j=k to 0
ZróbKMR (w, 2^j -> w+ 2^j) // dodaj 2^j do długości podsłowa
jeśli są dwie jednakowe liczby w tablicy w+2^j -> w=w+2^j to akceptujemy
i generalnie idea jest taka, żeby zwiększać, póki możemy.
Konkluzja końcowa: KMR jest „brzydki i nieprzyjazny” :P
