Tablica LCP

Cześć, tym razem walczę z tym zadaniem: http://pl.spoj.pl/problems/LCP/ w Javie.

Wiem, że jednym z pomysłów na nie jest stworzenie drzewa sufiksowego przy pomocy algorytmu Ukkonena. Jednak siedzę nad tym już dwa tygodnie i nie jestem w stanie tego wykonać, próbowałem również szukać implementacji drzewa sufiksowego z użyciem tego algorytmu, ale nie znalazłem odpowiednich, żeby móc wyciągnąć potem tą tablicę LCP.

W związku z powyższym mam pytanie następujące: czy jest inny równie efektywny sposób na zrobienie tego zadania? Dodam, że tablice sufiksowe nie przechodzą, algorytm z ich użyciem jest niestety zbyt wolny. Może istnieje jakiś inny algorytm, który pozwoliłby na szybkie obliczenie tej tablicy? Ew. może ma ktoś dobrą implementację drzew sufiksowych z użyciem algorytmu Ukkonena, przy użyciu której dałoby się również wyciągnąć taką tablicę LCP?

Dzięki za wszelką pomoc.

kyrtap1

Ja również z tym walczę, ale na razie bez efektu. Jak coś mi się uda zdziałać dam znać ;)

Naprawde nikt nic nie wie?

No ja niestety nic nie wymyśliłem w dalszym ciągu..

jakies postepy w sprawie tego zadania? tez mnie interesuje..

google podpowiada: http://www.siam.org/proceedings/alenex/2011/alx11_03_gogs.pdf

LCP da się wyliczyć w czasie liniowym z tablicy sufiksowej i z drzewa sufiksowego z odpowiednią organizacją liści (np jako lista uporządkowana alfabetycznie).

Tu jest szybka implementacja algorytmu do liczenia tablicy sufiksowej: http://code.google.com/p/libdivsufsort/

Oraz zbiór linków o podobnej tematyce: http://homepage3.nifty.com/wpage/links/index.html

Dzięki przejrzę :)