KMR

Doszły mnie słuchy, że niektórzy mają problemy ze zrozumieniem tego algorytmu (np przed chwilą patrzyłem na opis Bartka :P[i tak klepnąłem zanim przeczytałem to] ), no cóż, Agata opisała go dość mało obszernie i ciężko jest zrobić zadanie dodatkowe bazując tylko i wyłącznie na jej opisie, zatem (co prawda nieco późno) postanowiłem coś naskrobać ;)

OK, to co nam daje KMR? Ano w czasie O(n log n) otrzymujemy tablicę (nazwijmy ją DBR) o takim właśnie rozmiarze, dzięki której dość szybko możemy posortować podsłowa o danej długości naszego słowa.

Ale jak to działa? No więc tak, na początek "potniemy" sobie nasze słowo na "słowa" długości 1, tzn pojedyncze literki. Teraz je sobie gdzieś na boku sortujemy i każdej damy jakąś cyferkę. Np dla słowa aabbdeb zauważmy, że jakbyśmy wzięli po jednej literce każdego rodzaju i posortowali, to otrzymalibyśmy coś takiego: abde, teraz po prostu zastąpimy każdą literkę "a" jedynką, "b" dwójką itd, słowo wyglądać będzie tak: 1 1 2 2 3 4 2

To jest "pierwszy wiersz" naszej tablicy. Teraz będziemy chcieli posortować podsłowa o długości 2. Normalnie podzielilibyśmy całe słowo na słowa dwuliterowe i sortowali, ale możemy po prostu przedstawić je jako pary liczb, które przedstawiają podsłowa długości 1:
(1,1), (1,2), (2,2), (2,3), (3,4), (4,2), (2,0) [ Skąd się te liczby wzięły - jakieś wyjaśnienie? ]
Posortujmy je:
(1,1), (1,2), (2,0), (2,2), (2,3), (3,4), (4,2)
Teraz w miejscu wystąpienia pierwszej litery naszego słowa wstawimy jego numer w porządku leksykograficznym, tzn zamiast 11 wpiszemy 1, zamiast 12 wpiszemy 2, zamiast 20 wpiszemy 3 itd
1 2 4 5 6 7 3

Teraz analogicznie robimy dla podsłów długości 4, tzn przedstawiamy je jako dwucyfrowe liczby z powyżej wygenerowanej tablicy posłów długości 2, czyli:
(1,2), (2,4), (4,5), (5,6), (6,7), (2,0)
Sortujemy i powtarzamy wcześniejsze procesy.

OK, fajnie, mamy wygenerowane takie tabliczki dla podsłów długości potęg dwójki. I co z tego? Ano to, że jeśli chcemy otrzymać posortowane długości 7, to wystarczy "połączyć" cyferki z tablic, w których mamy zapisaną kolejność słów o długości 4, 2, 1, w ten sposób zamiast tworzyć słowa o długości "n", tworzymy liczby, które mają O(log n) cyfr, i które porównujemy w czasie stałym a nie O(n). [ $n$ elementów porównujemy w czasie $O(n)$, $n^2$ elementów porównujemy w czasie $O(n^2)$ itp. to czemu $log n$ elementów w czasie stałym a nie $O(log n)$ ? ]
chodziło mi o to, że 2 elementy porównamy w czasie stałym, a nie w czasie O(n) gdzie n to długość elementu
2 elementy tak, ale sam napisałeś, że trzymamy log n cyfr (raczej liczb), które porównujemy i raczej musimy to zrobić po kolei, bo sposób ze scalaniem w jedną liczbę się szybko sypie.

Dodatkowo, zauważmy, że jeżeli w naszej tablicy nie wystąpi 2 razy ta sama liczba (jak w naszym przykładzie dla słów długości 2 oraz 4) to wszystkie słowa są różne, a jeżeli chcemy znaleźć najkrótszą taką długość, to kto nam broni sprawdzić słowa różnych długości i zobaczyć czy w ich tablicy wszystko jest różne? :) Ale już więcej nie podpowiadam ;)

Tutaj pseudokod:

void KMR()
{
    for (int i=0; i<n; i++)
        A[i]=para(para(litera[i],0), i);
    posortuj A i zapisz kolejność w DBF[0]

    for (int j=1,l=1; l<n; j++,l*=2)  //2^j to długość podsłów jakie rozpatrujemy, "l" to również ich długość
    {
        for (int i=0; i<(n-l); i++)
            A[i]=para(para(DBF[j-1][i],DBF[j-1][i+l]), i) //tworzymy parę liczb, hash naszego słowa, który jest parą hashy krótszych podsłów, oraz numer rozpatrywanego podsłowa
        for (int i=n-l; i<n; i++)
            A[i]=para(para(DBF[j-1][i],0),i) //a to dla podsłów, które swoją długością wychodzą poza słowo 
        posortuj A i zapisz kolejność w DBF[j]
    }
}

[ Co do linii 8:
jeśli DBF[j-1][i1] = 66, DBF[j-1][i1+l] = 6
oraz DBF[j-1][i2] = 60, DBF[j-1][i2+l] = 66
to przypadkiem nie wychodzą Ci tym sposobem dwa identyczne hashe dla zupełnie różnych słów…? ]

no cóż, my bad, w moim kodzie po prostu hashuję łącząc w pary, a pisząc to pomyślałem, że można w powyższy sposób, ale cóż, sprawdza sięprzecież tylko jak mamy same cyfry, swoją drogą, co Cię tak na 666 wzięło? :>
[ Jak mamy cyfry to się sprawdza, lecz rzadko kiedy mamy do czynienia w zadaniu z ograniczeniem $n <= 9$, więc lepiej umieć klepać przypadek ogólny niż szczególny. A 666 to Mała Święta Liczba ( Link ) dlatego jej użyłem. ]
Jak już posortujemy A, to zapisujemy kolejność następująco, DBF[j][druga_liczba_z_pary A[0]]=1, DBF[j][druga_liczba_z_pary A[1]]=2, itd, chyba że (druga_liczba_z_pary A[i])==(druga_liczba_z_pary A[i+1]), wtedy DBF[j][(druga_liczba_z_pary A[i])]=DBF[j][(druga_liczba_z_pary A[i+1])]

[ Krig ]

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License