ASD Ćwiczenia 14

Zadanie 1

Dane sa teksty x, y, oblicz najdłuższy tekst z, który jest jednocześnie podsłowem x, y , z = nwpodsłowo(x,y)

Rozwiązanie

Konstruujemy drzewo sufiksowe dla tekstu x#y$. nwpodsłowo(x,y) odpowiada węzłowi w drzewie, który reprezentuje najdłuższe podsłowo, oraz z którego prowadzą ścieżki do liści reprezentujących numer sufiksu zaczynającego się w x, i numer sufiksu zaczynającego się w y. Drzewo trzeba odpowiednio przeprocessować bottom-up, żeby można było potem łatwo wyliczyć odpowiedni węzeł. Podobnie rozwiazujemy dla wiely słów x,y ,.. .

Zadanie ?

???????

Rozwiązanie

????????????.