A. Malinowski, W. RytterA. MalinowskiPaweł Wolff
Treść zadaniaOpracowanieProgram wzorcowy

Porównywanie naszyjników

W Bajtocji żyje bardzo znany jubiler Bajtazar. Zajmuje się on wyrobem naszyjników. Naszyjniki są zrobione z drogocennych kamieni nanizanych na nitkę. Do wyrobu naszyjników używa się 26-ciu rodzajów kamieni, będziemy je oznaczać małymi literami alfabetu (angielskiego): a, b, ..., z. Bajtazar postawił sobie za punkt honoru, aby nigdy nie wykonać dwóch takich samych naszyjników i przechowuje opisy wykonanych przez siebie naszyjników. Niektóre z tych naszyjników są bardzo długie. Dlatego też ich opisy mają skróconą postać. Każdy opis składa się z szeregu wielokrotnie powtórzonych sekwencji kamieni (wzorów). Opis naszyjnika to ciąg wzorów wraz z liczbami ich powtórzeń. Każdy wzór jest opisany za pomocą sekwencji liter reprezentujących kamienie tworzące wzór. Przykładowo, opis: abc 2 xyz 1 axc 3 reprezentuje naszyjnik abcabcxyzaxcaxcaxc powstały przez dwukrotne powtórzenie wzoru abc, jednokrotne wystąpienie wzoru xyz i trzykrotne powtórzenie wzoru axc. Sprawę dodatkowo utrudnia fakt, iż naszyjniki nie mają widocznego początku, ani końca i można je dowolnie obracać w kółko. Powyższy opis reprezentuje również np. naszyjniki cabcxyzaxcaxcaxcab oraz xcaxcaxcabcabcxyza.

Zadanie

Napisz program, który:

Wejście

W pierwszym i drugim wierszu pliku tekstowego nas.in znajdują się opisy naszyjników, po jednym w wierszu. Każdy z nich składa się z sekwencji liczb całkowitych i słów złożonych z małych liter alfabetu angielskiego, pooddzielanych pojedynczymi odstępami. Opis naszyjnika składa się z liczby całkowitej n równej liczbie wzorów występujących w opisie naszyjnika (1 le n le 1,000), po której występuje n opisów powtórzeń wzorów. Opis powtórzeń i-tego wzoru składa się z: liczby całkowitej li równej długości wzoru ( 1 le l_i le 10,000), słowa si złożonego z li małych liter alfabetu (angielskiego) a, ..., z, reprezentującego wzór oraz liczby całkowitej ki równej liczbie powtórzeń wzoru si (1 le k_i le 100,000). Wiadomo, że suma liczb li (dla i = 1, ..., n) nie przekracza 10 000.

Wyjście

Twój program powinien zapisać, w pierwszym i jedynym wierszu pliku wyjściowego nas.out, słowo ``TAK'', jeśli obydwa opisy przedstawiają taki sam naszyjnik, lub słowo ``NIE'', w przeciwnym przypadku.

Przykład

Dla pliku wejściowego nas.in 
3 3 abc 2 3 xyz 1 3 axc 3
4 4 cabc 1 4 xyza 1 3 xca 3 1 b 1
poprawną odpowiedzią jest plik wyjściowy nas.out 
TAK

Zmiany w treści zadania

Podczas zawodów dokonano następującej zmiany w treści zadania:

Naszyjniki powstałe jeden z drugiego przez odwrócenie kolejności kamieni nie muszą być identyczne, a więc np. opisy `abc' i `cba' nie reprezentują tego samego naszyjnika.

Rozwiązanie

Zadanie sprowadza się do sprawdzenia, czy dwa dane słowa (ciągi znaków) są cyklicznie równoważne, to znaczy, czy jedno można otrzymać z drugiego przez jego cykliczne przesunięcie. Nietrudno zauważyć, że mające takie same długości słowa u i w są cyklicznie równoważne wtedy i tylko wtedy, gdy u występuje jako podsłowo słowa wcdot w (gdzie cdot oznacza konkatenację, czyli sklejenie słów). Nasz problem można by zatem rozwiązać w czasie proporcjonalnym do długości badanych słów, stosując efektywny algorytm wyszukiwania wzorca w tekście. Znane są dość wyrafinowane algorytmy wyszukiwania wzorca w czasie liniowym bez użycia pomocniczych tablic (zob. np. [10]), jednak cykliczną równoważność można sprawdzić znacznie prościej (zob. [11]):

Wprowadźmy oznaczenia:

1{ Algorytm sprawdzania, czy u powstaje przez cykliczne przesunięcie w }
2{ Niech x = uu#, y = ww!, n=<i>u</i> }
3begin
4        i := 0; j := 0; k := 1;
5        while (i < n) and (j < n) and (k leq n) do
6        begin
7                k := 1;
8                while x[i+k] = y[j+k] do
9                        k := k+1;
10                if k leq n then
11                        if x[i+k] > y[j+k] then
12                                i := i+k
13                        end
14                                j := j+k
15        { Niezmiennik: [1..i]subseteq D1, [1..j]subseteq D2 }
16        end
17end;
18{ u jest cyklicznym przesunięciem w wtedy i tylko wtedy, gdy k > n }

Algorytm działa w czasie liniowym względem n, a jego poprawność wynika z podanego niezmiennika oraz z faktu, że jeśli D1 = [1..n] lub D2 = [1..n], to słowa u i w nie są cyklicznie równoważne.

Dodatkową trudność w zadaniu stanowi to, że opisy naszyjników są podane w formie skompresowanej. Żeby uzyskać program działający w czasie proporcjonalnym nie do faktycznego rozmiaru samych naszyjników, ale raczej do rozmiaru ich opisów, musimy odpowiednio zaimplementować pętlę w wierszach 8-9. W naszym przypadku wystarczy, żebyśmy potrafili efektywnie rozstrzygać, czy któreś ze słów al, br (gdzie al oznacza konkatenację l kopii słowa a) jest prefiksem (czyli fragmentem początkowym) drugiego słowa. Nietrudno pokazać, że jeśli |a^l|,|b^r|geq|a|+|b..., to powyższy warunek jest równoważny temu, że acdot b = bcdot a. Stąd wynika, że w celu stwierdzenia, czy któreś ze słów al, br jest prefiksem drugiego, wystarczy porównać tylko |a|+|b| początkowych liter tych słów.

Usprawnienia wymagają jeszcze wiersze 12 i 14 w algorytmie. Z podanego niezmiennika wynika, że jeśli na pozycji i+k (odpowiednio j+k) mamy do czynienia z co najmniej drugim powtórzeniem pewnego wzoru, to bez zaburzenia niezmiennika możemy od razu przeskoczyć do ostatniego powtórzenia tego wzoru.

Testy

Do sprawdzania rozwiązań zawodników użyto 11 grup testów (po 3 testy w każdej grupie). Oto ich krótka charakterystyka: