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