Haku loppuosataulukosta

Hakutietorakenteen perustana on aakkosjärjestykseen lajiteltu kaikki tekstin $S$ loppuosat sisältävä taulukko $Pos$. Taulukko $Pos$ ei sisällä itse loppuosia, vaan ainoastaan viittauksia loppuosan alkupositioon tekstissä $S$. Taulukon $Pos$ muodostaminen käsitellään myöhemmin.

Koska taulukko $Pos$ on aakkosjärjestyksessä, siellä ovat myös kaikki samalla merkkijonolla alkavat loppuosat peräkkäin. Näin kaikkien $P$:n esiintymien löytämiseksi riittää etsiä taulukosta ensimmäinen ja viimeinen $P$:llä alkava loppuosa. Tämä voidaan tehdä yksinkertaisella binäärihaulla $O(m \log n)$ ajassa.

Binäärihakua voidaan tehostaa vähentämällä symbolien välisiä vertailuja. Olkoon binäärihaarukan vasemman reunan indeksi $L$, vertailtavan loppuosan indeksi $M$ ja oikean reunan indeksi $R$. Merkitään merkkijonojen $w$ ja $v$ pisimmän yhteisen alkuosan pituutta $lcp(v,w)$:llä. Olkoon $l$ binäärihaarukan vasemman puolen ja $P$:n yhteisen alkuosan pituus $l=lcp(S_{Pos[L]},P)$ ja $r$ vastaavasti oikean puolen ja $P$:n yhteisen alkuosan pituus $r=lcp(P,S_{Pos[R]})$. Jokaisella binäärihaun iteraatiolla voidaan $P$:n ja $S_{Pos[M]}$:n vertailun yhteydessä laskea joko $l$ tai $r$ valmiiksi seuraavaa iteraatiota varten, toisen säilyessä samana. Koska loppuosat ovat aakkosjärjestyksessä loppuosataulukon kohdissa $L$, $M$ ja $R$ sijaitsevien loppuosien yhteisen alkuosan pituuden täytyy olla vähintään $h=min(l,r)$. Näin ollen loppuosan $S_{Pos[M]}$ ja merkkijonon $P$ vertailussa voidaan ohittaa $h$ symbolia.

Symbolien vertailuja voidaan edelleen vähentää ottamalla käyttöön kaksi aputaulukkoa. Merkitään yhtä binäärihaun tilaa kolmikolla $(L_M, M, R_M)$. Näitä kolmikoita on täsmälleen $n-2$ kappaletta (yksi jokaista binäärihaarukan mahdollista keskipistettä $M$ kohden). Otetaan käyttöön kaksi aputaulukkoa, jotka sisältävät binäärihaarukan keskipisteen ja reunojen pisimpien yhteisten alkuosien pituuden: $Llcp[M]=lcp(S_{Pos[L_M]}, S_{Pos[M]})$ ja $Rlcp[M]=lcp(S_{Pos[M]}, S_{Pos[R_M]})$. Nämä taulukot voidaan muodostaa triviaalisti, mutta tällöin muodostamisen aikavaatimus on pahimmillaan $O(n^2)$, vaikka keskimääräinen aikavaatimus on $O(n)$. Tehokkaampi muodostusalgoritmi on esitelty artikkelissa [MM93]. Oletetaan, että $l<=r$. Tällöin binäärihaun iteraatio voidaan toteuttaa seuraavasti:

Tapaus 1

$Llcp[M]>l$
Tässä tapauksessa $lcp(S_{Pos[M]},S_{Pos[L]}) > lcp(S_{Pos[L]},P)$, joten $P$:n täytyy löytyä binäärihaarukan oikeasta puoliskosta ja $l$ säilyy ennallaan.

Tapaus 2

$Llcp[M]=l$
Tässä tapauksessa hahmon ja haarukan keskipisteen ensimmäiset $l$ symbolia ovat samat. $P$:n sijainnin selvittämiseksi täytyy siis verrata $P$:n ja $S_{Pos[M]}$:n symboleita kohdasta $l$ eteenpäin, aivan kuten normaalissa binäärihaussa. Kun $P$:n sijainti binäärihaarukassa on selvinnyt, myös $l$:n tai $r$:n uusi arvo on selvinnyt.

Tapaus 3

$Llcp[M]<l$
Koska hahmon ja haarukan vasemman reunan pisimmän yhteisen alkuosan pituus on suurempi kuin haarukan keskipisteen ja vasemman reunan yhteisen alkuosan pituus, on selvää, että hahmon täytyy löytyä haarukan vasemmalta puolelta ja $r$:n uusi arvo on $Llcp[M]$.

Vastaavasti toimitaan, kun $l>r$. Tällä algoritmilla yhden symbolin vertailujen lukumääräksi saadaan enintään $m + \lceil \log_2(n-1) \rceil$ ja algoritmin aikavaatimukseksi $O(m+\log n)$ pahimmassa tapauksessa.