Sufiksno stablo
Sufiksno stablo predstavlja strukturu podataka koja opisuje internu strukturu stringa (niske) na vrlo iscrpan način. Sufiksno stablo može da se upotrebi da bi se rešio problem tačnog traženja za linerano vreme (postižući istu složenost u najgorem slučaju koju su postigli algoritmi KMP (Knuth-Morris-Pratt) i Bojer-Mur (Boyer-Moore), ali njihova prednost je u mogućnosti primene u algoritmima linearne složenosti za probleme sa stringovima složenijim od tačnog traženja. Štaviše, sufiksna stabla obezbeđuju most između problema tačnog traženja i približnog traženja.

Istorija 
Autor prvog algoritma za konstrukciju sufiksnih stabala linearne vremenske složenosti je Vajner (Weiner) 1973. godine, pri čemu je on za to stablo koristio termin stablo pozicija. Drugačiji, i što se tiče štednje prostora prilikom gradnje sufiksnih stabala bolji algoritam, dao je MekKrejt (McCraight) nekoliko godina kasnije. Nakon toga, Ukonen (Ukkonen) je razvio konceptualno drugačiji linerani algoritam za izgradnju sufiksnih stabala koji ima sve prednosti MekKrejtovog algoritma (a detaljnija analiza pokazuje da se on može smatrati varijantom MekKrejtovog algoritma), ali nudi mnogo jednostavnije objašnjenje.

Ovi algoritmi su linearne vremenske složenosti za azbuke konstantne dužine, i u najgorem slučaju imaju vremensku složenost .
Farah (Farach) je 1997. osmislio prvi algoritam za konstrukciju sufiksnih stabala koji daje optimalne rezultate za azbuke bilo kojih veličina. Farahov algoritam je postao osnova za sve novije algoritame za konstrukciju sufiksnih stabala i nizova.

Definicija 
Sufiksno stablo za string  dužine znakova  je korensko orijentisano stablo sa tačno  listova numerisanih od  do . Svaki unutrašnji čvor različit od korena ima najmanje dva sina i svaka grana je označena nepraznim podstringom za . Nikoje dve grane koje izlaze iz čvora ne mogu da imaju oznake grane koje počinju istim znakom. Pošto ne postoji sufiksno stablo koje zadovoljava datu definiciju za sve stringove, na  se dodaje jedan znak za kraj, koji nije u alfabetu, najčešće A$. Ovim se osigurava da ni jedan sufiks konačnog stringa ne može da bude prefiks ni jednog drugog sufiksa.
Ključna osobina kod sufiksnih stabala je ta, da za svaki list , konkatenacija oznaka grana na putu od korena do lista , je jednaka sufiksu  koji počinje na poziciji . Odnosno, da je  .

Uopšteno sufiksno stablo 
Uopšteno sufiksno stablo je sufiksno stablo za više reči i sadrži sve sufikse iz te grupe reči. Svaka reč u ovakvom stablu mora biti završena različitim terminalnim simbolom ili rečju.

Složenost algoritma 
Za azbuke konstantne veličine, složenost algoritma sufiksnog stabla  dužine  je . Za slučaj velike azbuke složenost se povećava na .

Složenost za azbuke konstantne veličine 
Za sufiksno stablo stringa  dužine , ili generalizovano sufiksno stablo niza stringova  ukupne dužine  može se:

 Pretraživati
 Da li je string  dužine  podstring, za vreme .
 Pronaći prvo pojavljivanje sekvence stringova  ukupne dužine  kao podstringova, za vreme .
 Pronaći svih z pojavljivanja sekvence stringova  ukupne dužine  kao podstringova, za vreme .
 Tražiti regularni izraz P za vreme linearno .
 Za svaki sufiks sekvence , naći dužinu najdužeg poklapanja prefiksa iz  sa , za vreme . Ovo se naziva statistika poklapanja za 
 Tražiti svojstva stringova
 Naći najduži zajednički podstring stringova  i  za vreme .
 Naći LZW dekompoziciju za vreme .
 Naći najduže ponavljajuće podstringove za vreme .
 Naći najponavljanije stringove odredjene dužine za vreme .
 Naći najkraće stringove iz  koji se ne pojavljuju u , za vreme , ako postoji  takvih stringova.
 Naći najkraće podstringove koji se pojavljuju samo jednom za vreme .
 Naći, za svako , najkaraći podstring  koji se ne pojavljuje nigde drugde u  za vreme .

Primene 
Sufiksna stabla imaju siroku primenu u rešavanju problema pri editovanju i pretrazi teksta, kompjuterskoj biologiji i drugim oblastima. Neka od primarnih polja primene su:

 Traženje najdužeg ponavljajućeg podstringa
 Traženje najdužeg zajedničkog podstringa
 Traženje najdužeg palindorma u stringu

Jedno od osnovnih polja primene sufiksnih stabala je bioinformatika. Proučavanje genoma je u najvećoj meri zasnovano na pretraživanju stringova i nalaženju određenih uzoraka u okviru njih. Sufiksna stabla se takodje primenjuju na polju kompresije podataka i neke vrste LZW kompresije koriste sufiksna stabla (LZSS).

Konstrukcija sufiksnog stabla 
Esko Ukonen (Esko Ukkonen) je napravio algoritam za konstrukciju sufiksnog stabla u linearnom vremenu koji je konceptualno najlakši algoritam za konstrukciju u linearnom vremenu.

Ukonenov algoritam konstruiše implicitno sufiksno stablo  za svaki prefiks  za , počevši od  uvećava za i dok stablo  ne bude konstruisano. Pravo sufiksno stablo  za je konstruisano iz  a vreme potrošeno za ceo algoritam je . Ukonenov algoritam inicijalno konstruiše stablo u vremenu  da bi se konstruisala sva stabla  a zatim se optimizovanjem njegove implementacije dobija vremenski nivo složenosti .

Osnovna struktura Ukonenovog algoritma 
 Konstruiše stablo 
 for i=1 to m-1
 begin {faza i+1 }
       for j=1 to i+1
             begin {produženje j}
             Polazeći od korena nalazi se kraj puta označenog sa u tekućem stablu.
             Ako je potrebno, taj put se produžava dodavanjem znaka ,
             i time osigurava da je string u stablu.
       end;
 end;

Za razliku od Ukonenovog algoritma, Vajnerov algoritam počinje celim stringom . Kao i kod Ukonenovog algoritma, unosi se po jedan sufiks u rastuće stablo, ali u bitno različitom rasporedu. Vajnerov algoritam konstruiše stabla od  na dole do .

Literatura 

 -{Gusfield, Dan (1999), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press. .}-
 .
 .
 .
 .

Стабла (структуре података)
Sufiksno stablo predstavlja strukturu podataka koja opisuje internu strukturu stringa ( niske ) na vrlo iscrpan način . Sufiksno stablo može da se upotrebi da bi se rešio problem tačnog traženja za linerano vreme ( postižući istu složenost u najgorem slučaju koju su postigli algoritmi KMP ( Knuth-Morris-Pratt ) i Bojer-Mur ( Boyer-Moore ) , ali njihova prednost je u mogućnosti primene u algoritmima linearne složenosti za probleme sa stringovima složenijim od tačnog traženja . Štaviše , sufiksna stabla obezbeđuju most između problema tačnog traženja i približnog traženja . Istorija Autor prvog algoritma za konstrukciju sufiksnih stabala linearne vremenske složenosti je Vajner ( Weiner ) godine , pri čemu je on za to stablo koristio termin stablo pozicija . Drugačiji , i što se tiče štednje prostora prilikom gradnje sufiksnih stabala bolji algoritam , dao je MekKrejt ( McCraight ) nekoliko godina kasnije . Nakon toga , Ukonen ( Ukkonen ) je razvio konceptualno drugačiji linerani algoritam za izgradnju sufiksnih stabala koji ima sve prednosti MekKrejtovog algoritma ( a detaljnija analiza pokazuje da se on može smatrati varijantom MekKrejtovog algoritma ) , ali nudi mnogo jednostavnije objašnjenje . Ovi algoritmi su linearne vremenske složenosti za azbuke konstantne dužine , i u najgorem slučaju imaju vremensku složenost \ . Farah ( Farach ) je osmislio prvi algoritam za konstrukciju sufiksnih stabala koji daje optimalne rezultate za azbuke bilo kojih veličina . Farahov algoritam je postao osnova za sve novije algoritame za konstrukciju sufiksnih stabala i nizova . Definicija Sufiksno stablo za string dužine znakova je korensko orijentisano stablo sa tačno listova numerisanih od do \ . Svaki unutrašnji čvor različit od korena ima najmanje dva sina i svaka grana je označena nepraznim podstringom za \ . Nikoje dve grane koje izlaze iz čvora ne mogu da imaju oznake grane koje počinju istim znakom . Pošto ne postoji sufiksno stablo koje zadovoljava datu definiciju za sve stringove , na se dodaje jedan znak za kraj , koji nije u alfabetu , najčešće A$ . Ovim se osigurava da ni jedan sufiks konačnog stringa ne može da bude prefiks ni jednog drugog sufiksa . Ključna osobina kod sufiksnih stabala je ta , da za svaki list , konkatenacija oznaka grana na putu od korena do lista , je jednaka sufiksu koji počinje na poziciji \ . Odnosno , da je \ . Uopšteno sufiksno stablo Uopšteno sufiksno stablo je sufiksno stablo za više reči i sadrži sve sufikse iz te grupe reči . Svaka reč u ovakvom stablu mora biti završena različitim terminalnim simbolom ili rečju . Složenost algoritma Za azbuke konstantne veličine , složenost algoritma sufiksnog stabla dužine je \ . Za slučaj velike azbuke složenost se povećava na \ . Složenost za azbuke konstantne veličine Za sufiksno stablo stringa dužine , ili generalizovano sufiksno stablo niza stringova ukupne dužine može se : Pretraživati Da li je string dužine podstring , za vreme \ . Pronaći prvo pojavljivanje sekvence stringova ukupne dužine kao podstringova , za vreme \ . Pronaći svih z pojavljivanja sekvence stringova ukupne dužine kao podstringova , za vreme \ . Tražiti regularni izraz P za vreme linearno \ . Za svaki sufiks sekvence , naći dužinu najdužeg poklapanja prefiksa iz sa , za vreme \ . Ovo se naziva statistika poklapanja za Tražiti svojstva stringova Naći najduži zajednički podstring stringova i za vreme \ . Naći LZW dekompoziciju za vreme \ . Naći najduže ponavljajuće podstringove za vreme \ . Naći najponavljanije stringove odredjene dužine za vreme \ . Naći najkraće stringove iz koji se ne pojavljuju u , za vreme , ako postoji takvih stringova . Naći najkraće podstringove koji se pojavljuju samo jednom za vreme \ . Naći , za svako , najkaraći podstring koji se ne pojavljuje nigde drugde u za vreme \ . Primene Sufiksna stabla imaju siroku primenu u rešavanju problema pri editovanju i pretrazi teksta , kompjuterskoj biologiji i drugim oblastima . Neka od primarnih polja primene su : Traženje najdužeg ponavljajućeg podstringa Traženje najdužeg zajedničkog podstringa Traženje najdužeg palindorma u stringu Jedno od osnovnih polja primene sufiksnih stabala je bioinformatika . Proučavanje genoma je u najvećoj meri zasnovano na pretraživanju stringova i nalaženju određenih uzoraka u okviru njih . Sufiksna stabla se takodje primenjuju na polju kompresije podataka i neke vrste LZW kompresije koriste sufiksna stabla ( LZSS ) . Konstrukcija sufiksnog stabla Esko Ukonen ( Esko Ukkonen ) je napravio algoritam za konstrukciju sufiksnog stabla u linearnom vremenu koji je konceptualno najlakši algoritam za konstrukciju u linearnom vremenu . Ukonenov algoritam konstruiše implicitno sufiksno stablo za svaki prefiks za , počevši od uvećava za i dok stablo ne bude konstruisano . Pravo sufiksno stablo za je konstruisano iz a vreme potrošeno za ceo algoritam je \ . Ukonenov algoritam inicijalno konstruiše stablo u vremenu da bi se konstruisala sva stabla a zatim se optimizovanjem njegove implementacije dobija vremenski nivo složenosti \ . Osnovna struktura Ukonenovog algoritma Konstruiše stablo for i=1 to m-1 begin { faza i+1 } for j=1 to i+1 begin { produženje j } Polazeći od korena nalazi se kraj puta označenog sa u tekućem stablu . Ako je potrebno , taj put se produžava dodavanjem znaka , i time osigurava da je string u stablu. end ; end ; Za razliku od Ukonenovog algoritma , Vajnerov algoritam počinje celim stringom \ . Kao i kod Ukonenovog algoritma , unosi se po jedan sufiks u rastuće stablo , ali u bitno različitom rasporedu . Vajnerov algoritam konstruiše stabla od na dole do \ . Literatura -{ Gusfield , Dan Algorithms on Strings , Trees and Sequences : Computer Science and Computational Biology , Cambridge University Press . \ . }- \ . \ . \ . \ . Стабла ( структуре података )