algorytm Ukkonena

Algorytm Ukkonena – algorytm budowy drzewa sufiksowego zaproponowany przez Esko Ukkonena w 1995 roku. Algorytm ten działa w czasie liniowym i jest algorytmem online. Algorytm zaczyna budowę od drzewa sufiksowego dla pierwszego znaku ciągu. W kolejnych krokach algorytm przekształca drzewo tak, aby było ono drzewem sufiksowym dla ciągu o 1 znak dłuższego. W momencie gdy algorytm doda ostatni znak ciągu drzewo sufiksowe jest gotowe. Taki sposób budowy drzewa zapewnia algorytmowi jego właściwość "on-line", poprzednie algorytmy budowały drzewo sufiksowe zaczynając od ostatniego znaku ciągu. Naiwna implementacja algorytmu ma złożoność O(n2), natomiast zaproponowana przez Ukkonena O(n).