Kometarz do zadania 1 z egzaminu z ASD 26 stycznia 2010
=======================================================

Oznaczmy n = |t| + |s|.
Rozwiązanie wzorcowe działa w czasie O(n). Bierzemy słowo
t#s$, gdzie # i $ są różnymi symbolami spoza alfabetu,
i konstruujemy dla tego słowa drzewo sufiksowe.
Dla każdego węzła v wyliczamy (od dołu do góry) wartość
dolar(v) - czy da się z tego węzła idąc w dół dojść
do znaku $ nie odwiedzając znaku #. Zauważmy, że każdemu
podsłowu słowa t, które nie jest podsłowem słowa s,
odpowiada taki węzeł w nieskompresowanym drzewie sufiksowym
słowa t#s$, dla którego dolar = false, i do którego od korzenia
można dojść nie odwiedzając znaku #. Takie węzły można łatwo
zliczyć mając funkcję dolar w skompresowanym drzewie sufiksowym.

Parę osób zrobiło to zadanie w czasie liniowym, zazwyczaj
w sposĂłb bardzo zbliĹźony do wzorcowego.
Wiele rozwiązań polegało na mniej lub bardziej skomplikowanym
wyszukiwaniu podsłów jednego słowa w drugim - te, w zależności
od złożoności, były oceniane od 1 do 3 pkt.

Bardzo popularnym rozwiązaniem było coś następującego:
tworzymy dwa drzewa sufiksowe (skompresowane) słowa t i słowa s
i następnie "jednocześnie" przechodzimy je DFSem. To jest
poprawne rozwiązanie, ale działające w czasie O(n^2) - mimo,
iż wiele osób twierdziło, że jest liniowe. Tak, liczba węzłów
w drzewach wynosi n - ale przejście po krawędzi, by sprawdzić,
czy teksty w obu drzewach się zgadzają, trwa. Spójrzmy na przypadek
t = s. Wówczas drzewa sufiksowe się całkowicie nałożą, i my je
DFSem całkowicie przejdziemy - zajrzymy do każdej literki na każdej
krawędzi - czyli obejrzymy tak naprawdę całe nieskompresowane
drzewo sufiksowe - a to ma rozmiar O(n^2). Takie rozwiązanie
dostawało 3 pkt, chyba że ktoś twierdził, że jest liniowe - wówczas
2 pkt.

Warto nadmienić, że z problemem powyższym można sobie poradzić
następująco: my de facto chcemy umieć szybko odpowiadać na pytania:
dla indeksu i w słowe t, dla indeksu j w słowie s, jak daleko słowa
t[i...] i s[j...] się zgadzają. To można odpowiadać w czasie stałym
robiąc tablicę LCA dla słowa t#s, lub w czasie O(log n) robiąc
algorytm KMR dla słowa ts.

Podsumowanie punktacji:
9 pkt   rozwiązanie O(n)
8 pkt   rozwiązanie O(n log n)
5 pkt   rozwiązanie O(n) z poważnymi błędami lub brakami:
         - zazwyczaj było to niepoprawny opis tego, co zliczamy
           w drzewie sufiksowym słowa t#s$
         - również tyle punktów otrzymywało rozwiązanie, które
           próbowało wpierw skonstruować drzewo sufiksowe s,
           a następnie "przy pomocy s skonstruować drzewo sufiksowe
           słowa t" - bez dokładniejszego opisu, co ono robi
           (to się da tak zrobić, de facto sprowadza się do zrobienia
            drzewa sufiksowego słowa st, i uważaniu w algorytmie
            Ukkonena, ale bez dokładniejszego opisu o co chodzi
            dostawało 5 pkt)
3 pkt   rozwiązanie O(n^2) lub O(n^2 log n) z poprawną analizą
        złożoności
2 pkt   rozwiązanie O(n^2) z niepoprawną analizą złożoności 
        (zazwyczaj było to stwierdzenie, że jest to liniowy algorytm)
        lub jej brakiem
1 pkt   poprawne rozwiązanie szybsze od absolutnie naiwnego