Omówienie zadania CzatBBB (I etap XXXI OI)
Podzadanie 1 - :
Limity w tym podzadaniu pozwalają na bezpośrednią symulację treści. Dla każdego -literowego podsłowa słowa zliczamy litery występujące po nim. Dzięki temu dla określonego -literowego sufiksu wiemy, jaka litera zostanie po nim dopisana. Po dopisaniu jakiejś litery do naszego słowa, jesteśmy w stanie zaktualizować informację o licznościach liter w czasie . Do takiego zliczania możemy wykorzystać drzewo trie lub kontener w języku .
Całkowita złożoność wyniesie , przy czym to rozmiar alfabetu.
Podzadanie 2 - :
Zamiast indeksować strukturę całymi słowami, to możemy indeksować ich haszami wielomianowymi (patrz np. opis w języku angielskim lub opis w książce "Przygody Bajtazara. 25 lat Olimpiady Informatycznej. Wybór zadań", PWN 2018). Musimy uważać na paradoks dnia urodzin, więc trzeba zastosować moduł rzędu lub dwa rzędu . Dzięki temu złożoność wyniesie .
Podzadania 3 oraz 4 - wcześniejsze wystąpienie sufiksu zawsze będzie istnieć i za każdym wystąpieniem będzie znajdować się ta sama litera:
Skoro wcześniejsze wystąpienia zawsze będą istnieć oraz zawsze będzie występować po nich ta sama litera, to jeżeli -literowym sufiksem jest słowo , a po nim -literowym sufiksem staje się słowo , to zawsze gdy następnym razem -literowym sufiksem będzie słowo , kolejnym -literowym sufiksem będzie ponownie . Rozważmy graf skierowany, którego wierzchołkami są -literowe słowa oraz istnieje krawędź ze słowa do słowa wtedy i tylko wtedy, gdy po sufiksie zawsze następuje sufiks . Graf ten składa się z wierzchołków o stopniu wyjściowym oraz odizolowanych wierzchołków o stopniu wejściowym i wyjściowym .
Nasze zadanie można sprowadzić do następującego problemu: Dany jest graf skierowany oraz wierzchołek o stopniu wyjściowym ; należy stwierdzić, w jakim wierzchołku się znajdziemy, jeżeli razy przejdziemy krawędzią, zaczynając od wierzchołka . Każda taka ścieżka od pewnego momentu (niekoniecznie po krawędziach) się zacykli. Po wyznaczeniu ścieżki do cyklu oraz cyklu (oba rozmiaru ) możemy wyznaczyć wierzchołek końcowy, a następnie cofnąć się odpowiednią liczbę razy, wyznaczając przy tym odpowiednie litery (od końca).
W zależności od użytej metody do budowy grafu rozwiązanie to ma złożoność obliczeniową lub .
Podzadanie 5 - , użyte są tylko litery i :
Okazuje się, że aby stwierdzić, jaka litera występuje po -literowym słowie wychodzącym już poza słowo , wystarczy sprawdzić, jaka litera najczęściej występuje po tym podsłowie wśród wszystkich wystąpień tego podsłowa ściśle wewnątrz słowa . Za każdym nowym wystąpieniem tego podsłowa, częstość wystąpienia najliczniejszej litery wzrasta o jeden, więc nadal jest największa, czyli przy kolejnym wystąpieniu tego -literowego podsłowa kolejna litera będzie taka sama. Oznacza to, że podejście grafowe z poprzedniego podzadania można zastosować i tutaj. Ponieważ alfabet jest dwuliterowy oraz , to możliwych słów jest co najwyżej . Jest to dostatecznie mało, aby skonstruować cały graf.
Podzadanie 6 -
Zbiór wierzchołków grafu osiągalnych z wierzchołka startowego tak naprawdę zawsze jest rozmiaru . Faktycznie, jeżeli -literowy sufiks nie występował wcześniej jako podsłowo słowa , to dopisujemy literę . To może się wydarzyć pod rząd co najwyżej razy - po -wszym dodaniu litery już zawsze będziemy dopisywać . Jeżeli natomiast -literowy sufiks występował w całości w słowie , to po dodaniu nowej litery, -literowy sufiks również będzie występować w całości w słowie - wiemy, że najczęściej występująca litera po jest również najczęściej występującą literą po wśród wszystkich wystąpień w całości w słowie i ma krotność przynajmniej , więc musi istnieć słowo w całości występujące w słowie .
Wynika z tego, że jest tylko różnych słów długości do rozpatrzenia i są to podsłowa słowa . Możemy sobie zatem pozwolić na konstrukcję interesującej nas części grafu i wyznaczenie w nim ścieżki do cyklu oraz cyklu, począwszy od zadanego wierzchołka startowego. Podsłowa reprezentujemy za pomocą identyfikatorów (hasze lub np. deterministyczny słownik podsłów bazowych KMR) i utrzymywać je w haszmapie (w przypadku haszy) lub w tablicy (w przypadku KMR). Ostateczne rozwiązanie ma złożoność lub w przypadku deterministycznym.