Tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą \(x[1 .. n]\), elementami której są symbole ze skończonego zbioru \( \Sigma\) (zwanego alfabetem). Liczba \(n=|x|\) jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.

Algorytmy na tekstach wyróżniają się tym, że wykorzystują specyficzne, kombinatoryczne własności tekstów. Okresem tekstu \(x\) jest każda niezerowa liczba naturalna \(p\) taka, że \(x[i]=x[i+p]\), dla każdego \(i\), dla którego obie strony są zdefiniowane. Przez \( per(x) \) oznaczmy minimalny okres \(x\). Zachodzi następująca ciekawa własność kombinatoryczna okresowości w tekstach.

Lemat ten wynika z poprawności algorytmu Euklidesa z odejmowaniem, który oblicza \(nwd(p,\, q)\). Zauważmy, że jeśli \(p > q\) są okresami, to \(p-q\) też jest okresem.

Lemat o okresowości można wzmocnić, osłabiając założenia.

Cyklicznym przesunięciem słowa \(x\) jest każde słowo postaci \(vu\), gdzie \(x = uv\). Zastanówmy się nad możliwą liczbą cyklicznych przesunięć danego słowa.

Słowo \(w\) nazywamy pierwotnym (nierozkładalnym), gdy nie można przedstawić \(w\) jako konkatenacji wielu (co najmniej 2) kopii tego samego słowa. Tzn. jeśli można zapisać \(w\) jako \(x^k\) takie, że \(k > 1\), to słowo \(w\) nie jest pierwotne. Z lematu o okresowości wynika następujący fakt.

Dowód

Przypuśćmy, że \(x\) ma dwa przesunięcia równe co do wartości (jako słowa): \(x = uv = u'v'\) oraz \(vu = v'u'\), gdzie \(u \neq u'\). Niech \(|u'| < |u|\). Wtedy \(u = u' \alpha,\, v'=\alpha \cdot v\) oraz \(vu'\alpha = \alpha vu'\). Zatem słowo \(\alpha \cdot v \cdot u' \cdot \alpha\) ma prefikso-sufiksy \(\alpha \cdot v \cdot u'\) oraz \(\alpha\). W konsekwencji tekst \(\alpha \cdot v \cdot u' \cdot \alpha\) ma dwa okresy rozmiaru \(r = \vert \alpha \vert \) oraz \(p= \vert vu'\alpha \vert \). Jednocześnie zachodzi: \(r+p = \vert\alpha \cdot v \cdot u' \cdot \alpha \vert\).

Z lematu o okresowości wynika, że tekst ma okres \(nwd(r,\, p)\), którego długość jest w szczególności mniejsza od \(p\), zatem \(x\) jest potęgą słowa krótszego od siebie i nie jest pierwotne. A zatem \(x\) nie może mieć dwóch takich samych przesunięć.

Pokażemy teraz proste zastosowanie w teorii liczb. W roku 1640 Pierre de Fermat pokazał następujący fakt.

Dowód

Definiujemy relację równoważności \(x \equiv y\) gdy \(x\) jest przesunięciem cyklicznym \(y\). Mówimy, że słowo jest unarne, jeśli wszystkie jego litery są takie same.

Niech \(S\) bedzie zbiorem słów nieunarnych długości \(p\) nad alfabetem \(\lbrace 1,\, 2,\ldots,\,n \rbrace \). Słowa te są pierwotne, gdyż ich długość jest liczbą pierwszą i nie są unarne. Zgodnie z poprzednim lematem każda klasa równoważności ma dokładnie \(p\) elementów. Klasy te są rozłączne. Moc zbiorów \(S\) jest równa \( n^p-n \) oraz \(S\) można podzielić na rozłączne podzbiory o tej samej mocy \(p\). Zatem moc \(S\) jest podzielna przez \(p\), a więc \(p\ |\ n^p-n\).

Prefikso-sufiksy i tablica \(P\)

Pojęciem dualnym do okresu jest prefikso-sufiks tekstu. Jest to najdłuższy właściwy (nie będący całym tekstem) prefiks tekstu \(x\) będący jednocześnie jego sufiksem. Oczywiste jest, że \(|x|-per(x)\) jest długością prefikso-sufiksu \(x\). Jeśli \(per(x)=|x|\) to prefikso-sufiksem \(x\) jest słowo puste o długości zerowej.

Oznaczmy przez \(P[k]\) rozmiar prefikso-sufiksu \(x[1..k]\). Zatem \(per(x)=n-P[n]\), gdzie \(n=|x|\).

Przedstawimy jeden z możliwych algorytmów liniowych obliczania tablicy \(P\). Jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymać korzystając z faktu:

Jeśli \(x[j] = x[t+1]\) oraz \(t = P[j-1]\), to \(P[j] = t+1\)

W algorytmie obliczania \(P[j]\) korzystamy z wartości \(P[k]\), dla \(k < j\).

P[0] := -1;
t := -1;
for j := 1 to m do begin
    while (t >= 0) and (x[t+1] <> x[j]) do
        t := P[t];
    t := t + 1;
    P[j] := t;
end;

Złożoność liniowa wynika stąd, że w każdej iteracji zwiększamy wartość \(t\) co najwyżej o jeden, a wykonanie każdej operacji \(t:=P[t]\) zmniejsza wartość \(t\) co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji \(t:=P[t]\) wykonujemy co najwyżej \(t\). Dowód poprawności pozostawiamy jako ćwiczenie.

Zastosowanie tablicy \(P\): liczenie maksymalnego sufiksu

Oznaczmy przez \(MaxSuffix(x)\) leksykograficznie maksymalny sufiks \(x\). Jeśli \(|x|=n\) to niech \(MaxSuffix(x)=x[s+1\ldots n]\). Przedstawimy jeden z możliwych algorytmów liniowych obliczania \(MaxSuffix(x)\). Algorytm ten pochodzi z pracy Lexicographically least circular substrings autorstwa K. S. Bootha i stanowi wersję algorytmu liczenia tablicy \(P\).

Korzystamy z następującego faktu:

Jeśli \(MaxSuffix(x)=z\), i \(MaxSuffix(xc)=z'c\), to \(z'\) jest prefikso-sufiksem \(z\).

W algorytmie obliczamy jednocześnie tablicę \(P\) dla tekstu \(x[s + 1\,\ldots j]\). Utrzymujemy niezmienik: mamy poprawaną tablicę \(P\) dla tekstu \(x[s + 1\,\ldots j]\) oraz \(x[s + 1\,\ldots j] = MaxSuffix(x[1\,\ldots j]).\)

P[0] := -1;
t := -1;
s := 0;
for j := 1 to m do begin
   while (t >= 0) and (x[s + t + 1] < x[j]) do begin
        s := j - 1 - t;
        t := P[t];
   end;
   while (t >= 0) and (x[s + t + 1] <> x[j]) do
        t := P[t];
    t := t + 1;
    P[j - s] := t;
end;

Zastosowanie tablicy \(P\): minimalne słowa o zadanej strukturze okresów

Niech \(Okresy(w)\) onacza zbiór długości okresów słowa \(w\). Rozważamy następujący problem: znaleźć minimalne leksykograficznie słowo \(u\) nad binarnym alfabetem spełniające \(Okresy(w) = Okresy(u)\).

Opisany algorytm jest wersją algorytmu pochodzącego od Vesa Halava, Tero Harju, Lucian Ilie, który kostruuje
jakikolwiek tekst binarny okresowo równoważny danemu słowu. Nasz algorytm podaje leksykograficznie minimalny
taki tekst, a pomimo tego (a może właśnie dzięki temu) jest prostszy.

Pierwszym krokiem jest policzenie zbioru okresów \(Okresy(w)\) tego słowa, po czym właściwie zapominamy o słowie \(w\). Zakładamy zatem odtąd, że znamy zbiór okresów słowa wejściowego. Pozostawiamy czytelnikowi jako proste ćwiczenie wyprowadzenie z lematu o okresowości dowodu następującego faktu.

Zamiast przetwarzać okresy wygodniej robić to dla prefikso-sufiksów: słów niepustych będących jednocześnie prefiksem i sufiksem tekstu. Oczywiście cały tekst także jest swoim prefikso-sufiksem.

Oznaczmy rosnący ciąg długości kolejnych prefikso-sufiksów słowa \(w\) przez \(\pi(w) = (p_1,\, p_2,\ldots,\, p_k)\), w szczególności \(p_k = n\). Ciąg \(\pi(w)\) łatwo wyliczyć znając zbiór okresów, zachodzi bowiem \(Okresy(w) = Okresy(v) \Leftrightarrow \pi(w) = \pi(v)\).

Oznaczmy minimalne leksykograficznie słowo, którego ciągiem długości prefikso-sufiksów jest \((p_1,\, p_2,\ldots,\, p_i)\) przez:
$$P_i = MinLex(p_1,\ldots,\, p_{i}).$$
Słowo to jest \(i\)-tym (w kolejności długości) prefikso-sufiksem wyniku.

Nieformalny opis algorytmu

Zasadnicza koncepcja algorytmu jest naturalna i narzucająca się - chcemy ,,wepchnąć'' w tekst jak największą liczbę zer celem uzyskania leksykograficznej minimalności. Algorytm opiera się zatem na zachłannym wpisywaniu \(0^+\) albo \(0^*1\) w te fragmenty tekstu, które nie są zdeterminowane przez prefikso-sufiksy w następującym sensie: każdy \(P_{i+1}\) musi się zaczynać od \(P_i\).

Początkowo mamy tekst długości \(n\) którego wszystkie pola są ,,puste''. Wypełniamy kolejne puste pola od końca wpisując prefikso-sufiksy, zaczynając od najkrótszego z nich, tzn. \(P_1\). Dla \(\pi = (p_1,\, p_2,\ldots,\ p_k)\) słowo \(P_{i+1}\) konstruujemy dopisując na początku \(P_i\) lub jego prefiks, jeśli jest za mało miejsca na całe \(P_i\). Niezapełnione pola tekstu zastępujemy leksykograficznie pierwszym ciągiem \(\Delta\), który nie wygeneruje nadmiarowego prefikso-sufiksu.

Obserwacja
Najciekawszą własnością algorytmu jest fakt, że wystarczy zawsze sprawdzić tylko dwie alternatywy na brakujący fragment:
$$\Delta \in \lbrace O^j,\, O^{j-1}1 \rbrace \text{ dla } j = p_{i+1} - 2 p_i$$.
Dzięki temu możliwy jest algorytm działający w czasie liniowym. Postawową operacją wykonywaną w algorytmie jest sprawdzenie którą z opcji na \(\Delta\) wybrać, aby nie wygenerował się nadmiarowy prefikso-sufiks.

Algorytm \(\mathbf{MinLex}(p_1,\, p_2, \ldots,\, p_k)\)

• if (\(p_1 = 1\)) then
  • \(P_1 := 0\)

  else

  • \(P_1 := 0^{p_1-1}1\);
• for \(i = 1\) to \(k-1\) do
  • \(j := p_{i+1} - 2 p_i\);
  • if (\(j \leq 0\)) then
    • \(P_{i+1} := \alpha P_i\), gdzie \(\alpha\) jest prefiksem \(P_i\) długości \(p_{i+1}-p_i\)

    else if (\(Pierwotny(P_i 0^j)\)) then

    • \(P_{i+1} := P_i 0^j P_i\)

  else

  • \(P_{i+1} := P_i 0^{j-1}1 P_i\);
• return \(P_k\);

Poprawność algorytmu

Zauważmy, że jeśli mamy sytuację gdy \(j > 0\) to wtedy \(P_i\) zawiera co najmniej jedną jedynkę. Poprawność algorytmu wynika z następujących dwóch faktów.

Fakt 1.
Niech \(j > 0\) oraz \(P\) będzie dowolnym binarnym tekstem zawierającym co najmniej jedną jedynkę. Wtedy \(u = P\, 0^j P\) ma (nadmiarowy) prefikso-sufiks o długości \(|P\,| < p < |u|\) wtedy i tylko wtedy gdy \(P\, 0^j\) nie jest pierwotny.

Uzasadnienie
Przypuśćmy, że istnieje nadmiarowy prefikso-sufiks \(P\,'\). Ten prefikso-sufiks nie może się zacząć wewnątrz aktywnego fragmentu \(O^j\), bo \(P\) zawiera jedynkę. Z drugiej strony jeśli \(P\,'\) zaczyna się w prefiksie \(P\) słowa \(u\), to na mocy lematu o okresowości słowo \(u\) ma (mały) okres, który jest krótszy od \(P\, 0^j\) i jest dzielnikiem długości tego słowa. Wynika to stąd, że tekst \(u\) miałby okresy o długościach \(| P\, 0^j|\) oraz \(|P\,'| \leq |P\,|\). Długość tekstu \(u\) jest nie mniejsza od sumy tych okresów i można wtedy zastosować lemat o okresowości.

Zatem jeśli \(P\, 0^j P\) ma nadmiarowy prefikso-sufiks, to \(P\, 0^j\) nie jest pierwotne. Łatwo można zauważyć implikację odwrotną, wtedy \(u\) ma nadmiarowy prefikso-sufiks o długości \(u - p\), gdzie \(p\) jest (małym) okresem \(P\, 0^j\). Kończy to uzasadnienie faktu.

Fakt 2.
Jeśli \(P\, 0^j\) nie jest pierwotny, to \(P\, 0^{j-1}1\) jest pierwotny. Uzasadnienie wynika z lematu o tekstach pierwotnych.

Złożoność algorytmu

Podstawowym problemem jest sprawdzenie czy tekst \(P_i 0^j\) jest pierwotny. W miarę konstruowania coraz większych prefikso-sufiksów, a więc jednocześnie prefiksów całego tekstu wynikowego, budujemy on-line tablicę wszystkich prefikso-sufiksów z algorytmu Knutha-Morrisa-Pratta. Dzięki tej tablicy znamy najkrótszy okres i możemy sprawdzić czy dany prefiks jest pierwotny. Zatem algorytm działa w czasie liniowym.

Na początek zajmiemy sie obliczaniem tablicy Prefikso-Sufiksów.

Przedstawimy jeden z możliwych algorytmów liniowych obliczania tablicy \(P\). Jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymać korzystając z faktu:

Jeśli \(x[j]=x[t+1]\) oraz \(t=P[j-1]\), to \(P[j]= t+1\)

W algorytmie obliczania \(P[j]\) korzystamy z wartości \(P[k]\), dla \(k < j\).

P[0] := -1;
t := -1;
for j := 1 to m do begin
    while (t >= 0) and (x[t+1] <> x[j]) do
        t := P[t];
    t := t + 1;
    P[j] := t;
end;

Złożoność liniowa wynika stąd, że w każdej iteracji zwiększamy wartość \(t\) co najwyżej o jeden, a wykonanie każdej operacji \(t:=P[t]\) zmniejsza wartość \(t\) co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji \(t:=P[t]\) wykonujemy co najwyżej \(t\). Dowód poprawności pozostawiamy jako ćwiczenie.

Algorytmy Morrisa-Pratta i Knutha-Morrisa-Pratta

Przedstawimy klasyczne algorytmy Morrisa-Pratta (w skrócie MP) oraz Knutha-Morrisa-Pratta (w skrócie KMP) dla problemu string-matchingu: obliczyć w w tekście \(y\) wszystkie (lub pierwsze) wystąpienia danego tekstu \(x\), zwanego wzorcem.

Algorytmy MP i KMP różnią się jedynie tym że jeden używa tablicy \(P\) a drugi \(P'\). Tablica \(P'\) jest bardziej skomplikowana, będziemy się zatem głównie koncentrować na algorytmie MP, poza wersją on-line (gdzie właśnie \(P'\) ma przewagę).

Oznaczmy \(m=|x|\), \(n=|y|\), gdzie \(m \le n\).

Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm MP przegląda tekst \(y\) od lewej do prawej, sprawdzając, czy jest zgodność na pozycji \(j+1\) we wzorcu \(x\) oraz na pozycji \(i+j+1\) w tekście \(y\). Jeśli jest niezgodność, to przesuwamy potencjalny początek (pozycja \(i\)) wystąpienia \(x\) w \(y\). Zakładamy, że algorytm zwraca na końcu wartość false, o ile nie zwróci wcześniej true.

i := 0;
j := 0;
while i <> n - m do begin
    while (j < m) and (x[j+1] = y[i+j+1]) do
        j := j + 1;
    if j = m then
        return true;
    i := i + j - P[j];
    j := max(0, P[j]);
end;

Uwaga: Algorytm działa podobnie gdy zamiast prefikso-sufiksów użyjemy tablicy \(P'\) silnych prefisko-sufksów. Algorytm w całości jest wtedy bardziej skomplikowany ze względu na trudniejszy preprocessing (liczenie \(P'\) jest trudniejsze od \(P\)).

Algorytm MP z tablicą \(P'\) zamiast \(P\) nazywamy algorytmem Knutha-Morrisa-Pratta i oznaczamy przez KMP.

Operacją dominującą w algorytmach KMP i MP jest operacja porównania symboli: \(x[j+1]=y[i+j+1]\). Algorytmy KMP i MP wykonują co najwyżej \(2n-m\) porównań symboli. Zauważmy, że dla danej pozycji w tekście \(y\) jest ona co najwyżej raz porównana z pewną pozycją we wzorcu w porównaniu pozytywnym (gdy symbole są równe). Jednocześnie każde negatywne porównanie powoduje przesunięcie pozycji \(i\) co najmniej o jeden, maksymalna wartość \(i\) wynosi \(n-m\), zatem mamy takich porównań co najwyżej \(n-m\), w sumie co najwyżej \(2n-m\) porównań.

Algorytm dla \(x=ab\), \(y=aa..a\) wykonuje \(2n-2\) porównań, zatem \(2n-m\) jest dolną i jednocześnie górną granicą na liczbę porównań w algorytmie.

Obserwacja: W wersji on-line algorytmu okaże się, że jest zdecydowana różnica między użyciem \(P'\) i \(P\); to właśnie jest motywacją dla wprowadzenia silnych prefikso-sufiksów.

Wersja on-line algorytmu KMP

Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole \(y\) i wypisujemy on-line (na bieżąco) odpowiedź:

• 0 - gdy dotychczas wczytany tekst nie zawiera x jako sufiks,
• 1 - jeśli zawiera.

j := 0;
repeat forever
begin
    read(symbol);
    while (j > -1) and (x[j+1] <> symbol) do
        j := Pp[j];
    j := j + 1;
    if j = m then begin
        write('1');
        j := Pp[m];
    end else
        write('0');
end;

Oznaczmy przez \(delay(m)\) maksymalną liczbę kroków algorytmu On-Line-KMP między wczytaniem symbolu i daniem odpowiedzi. Przez \(delay'(m)\) oznaczmy podobną wielkość, w sytuacji gdy zamiast tablicy \(P'\) użyjemy \(P\).

Wersja real-time algorytmu Morrisa-Pratta

Pokażemy teraz wersję algorytmu on-line, która działa w czasie rzeczywistym, tzn. czas reakcji między wczytaniem symbolu a daniem odpowiedzi jest \(O(1)\), niezależnie od rozmiaru alfabetu. Zamiast KMP użyjemy algorytmu MP, którego preprocessing jest prostszy.

Algorytm zachowuje się podobnie jak algorytm On-Line-KMP; podstawowa różnica polega na tym, że algorytm wkłada do kolejki wczytane symbole, które jeszcze nie są przetworzone w sensie algorytmu MP. Rysunek pokazuje relacje tego algorytmu do algorytmu MP. Symbole z wejścia najpierw wędrują do kolejki.

j := 0;
Kolejka.clear();
repeat forever { niezmiennik: |Kolejka| <= m - j }
begin
    read(symbol);
    Kolejka.push(symbol);
    write(OUTPUT(Kolejka, j));
end;

W celu skrócenia zapisów pojedynczych algorytmów rozbijamy algorytm na dwie części. Zasadnicza część jest zapisana jako osobna funkcja OUTPUT(Kolejka, j). Wynikiem funkcji jest 0 lub 1, w zależności od tego czy ostatnio wczytany symbol kończy wystąpienie wzorca \(x\). Zmienne \(Kolejka\), \(j\) są globalne.

output := 0;
repeat 2 times
begin
    if not Kolejka.empty() then begin
        if j = -1 then begin
            j := 0;
            Kolejka.pop();
        end else if  x[j+1] <> Kolejka.front() then
            j := P[j];
        else begin
            j := j + 1;
            Kolejka.pop();
        end;
        if j = m then begin { w tym momencie Kolejka jest pusta }
            output := 1;
            j := P[m];
        end;
    end;
end;

Poniższy dowód został opracowany przez Jakuba Radoszewskiego.

Zastanówmy się nad poprawnością tego algorytmu. Problem jaki musimy rozwiązać to właściwość algorytmu, którą nazwiemy opóżnieniem. Polega ona na tym, że w danym kroku algorytm może wciąż jeszcze rozważać właściwy prefiks aktualnego słowa i nie dotrzeć w ogóle do rozważenia bieżącej litery. Pokażemy jednak, że w momencie, kiedy nastąpi wystąpienie wzorca, kolejka zostanie opróżniona, co wystarczy do dowodu poprawności algorytmu.

Dowód przeprowadzimy nie wprost - załóżmy, że w tym kroku kolejka się nie opróżni i że jest to pierwsze wystąpienie wzorca, którego algorytm nie zdąża wyśledzić. Zacznijmy rozważanie działania algorytmu od ostatniego miejsca wcześniejszego od bieżącego, w którym kolejka się opróżnia. W tym momencie zachodzi \(j < m\) (nawet jeżeli w owym kroku było wystąpienie wzorca w tekście, to ten warunek i tak będzie po tym kroku spełniony) oraz \(|Kolejka| = 0\). Pokażemy, że odtąd aż do miejsca wystąpienia wzorca zachodzić będzie niezmiennik \(|Kolejka| < m - j\).

Zastanówmy się co się może wydarzyć w dowolnym, kolejnym kroku algorytmu, a co może zmienić wartość zmiennej \(j\):

• Może być dwukrotnie wywołana instrukcja j := P[j]. Wówczas \(|Kolejka|\) wzrasta o 1, \(m - j\) wzrasta co najmniej o 2, czyli niezmiennik dalej zachodzi.
• Moze być raz wywołana instrukcja j := P[j], a raz j := j + 1 (w jakiejkolwiek kolejności). Wówczas \(|Kolejka|\) się nie zmienia, \(m - j\) pozostaje bez zmian lub wzrasta, co nie zaburza niezmiennika.
• Mogą nastąpić dwie instrukcje powiększające \(j\) o 1. Wówczas \(|Kolejka|\) maleje o 2, \(m - j\) także maleje o 2, zatem niezmiennik pozostaje zachowany.

Kolejka nie może się opróżnić, gdyż zakładamy, że to nie nastąpi przed aktualnie rozważanym wystąpieniem wzorca. Instrukcja j := P[m] również nie może wystąpić, ponieważ oznaczałoby to wcześniejsze od rozważanego niezauważone przez algorytm wystąpienie wzorca w tekście.

Zatem niezmiennik jest zachowany od ostatniego momentu opróżnienia kolejki do momentu niezauważonego wystąpienia wzorca. W chwili przetworzenia literki, która powoduje wystąpienie zachodzi \(j = m\), czyli na mocy pokazanego niezmiennika \(|Kolejka| < m - m = 0\), \(|Kolejka| < 0\). To z kolei daje żądaną sprzeczność.

Oszczędna wersja algorytmu Morrisa-Pratta

Algorytm MP wykonuje co najmniej \(2n-m\) porównań symboli. Załóżmy, że są to operacje dominujące i spróbujmy zmniejszyć stały współczynnik \(2\) do \(\frac{3}{2}\). Na początku załóżmy, że \(x=ab\). Następujący algorytm znajduje wszystkie wystąpienia wzorca \(ab\) w tekście \(y\).

{ wzorcem jest 'ab' }
i := 0;
while i <= n - m do begin
    while y[i+2] <> 'b' do
        i := i + 1;
    if y[i+1] = 'a' then begin
        wypisz_wystąpienie;
        i := i + 2;
    end;
end;

Algorytm MP dla wzorca \(ab\) i tekstu \(aaa \ldots aa\) wykonywał \(2n-2\) porównań symboli, nowy algorytm jest lepszy. Algorytm Szukanie-ab wykonuje co najwyżej \(n\) porównań w tym przypadku, tak jest dla każdego tekstu w którym szukamy \(aab\).

Pozostawiamy jako ćwiczenie policzenie maksymalnej liczby porównań dla tego algorytmu (wzorzec \(ab\)). Widać, że podstawowa idea to sprawdzanie najpierw pierwszego symbolu wzorca różnego od poprzednich.

Uogólnimy algorytm na dowolne wzorce. Niech \(x\) zawiera co najmniej dwa różne symbole, \(x=a^kx'\), gdzie \(a\ne b\). Oznaczmy \(x'=b\alpha\) ,,skrócony wzorzec''.

Podamy nieformalny zarys działania oszczędniejszej wersji algorytmu MP, w której osobno szukamy \(x'\) i osobno części \(a^k\).

Niech MP' będzie taką wersją algorytmu MP, w której szukamy jedynie wzorca \(x'\), ale tablica \(P\) jest obliczona dla wzorca \(x\). Jeśli \(j > 0\) i \(shift \le k\), to wykonujemy przesunięcie potencjalnego początku i wzorca w \(y\) o \(k+1\), gdzie \(shift=j-P[j]\).

Inaczej mówiąc, nie szukamy wszystkich wystąpień \(x'\), ale jedynie takich, które mają sens z punktu widzenia potencjalnego znalezienia na lewo ciągu \(a^k\).

Tak zmodyfikowany algorytm MP' zastosujemy jako część algorytmu Oszczędny-MP.

Algorytm Oszczędny-MP

• wzorcem jest \(x=a^kb\alpha\)
• znajdź wszystkie wystąpienia części \(bz\) algorytmem MP zmodyfikowanym powyżej;
• Dla każdego wystąpienia \(b\alpha\) sprawdzamy, czy bezpośrednio na lewo jest \(a^k\);
• Pozycji tekstu sprawdzonych z wynikiem pozytywnym następny raz nie sprawdzamy.

Graficzna ilustracja działania algorytmu Oszczędny-MP jest pokazana na rysunku.

Pozostawiamy jako ćwiczenie dokładny zapis algorytmu oraz dokładniejszy dowód tego, że algorytm Oszczędny-MP wykonuje co najwyżej \(\frac{3}{2}n\) porównan.

Ogólna idea jest przedstawiona na rysunku.

Niech zasadniczymi operacjami będą operacje sprawdzania pierwszego \(b\) na danej pozycji tekstu \(y\) oraz te sprawdzania symboli, które są z wynikiem pozytywnym. Takich operacji jest co najwyżej \(n\). Pozostałe operacje to:

1. sprawdzanie w części \(\alpha\) z wynikiem negatywnym; wtedy przesuwamy wzorzec co najmniej o \(k\),
2. sprawdzanie części \(a^k\) na lewo od ,,pozytywnego'' \(b\) (w kwadraciku na rysunku), na pozycjach, gdzie wcześniej było sprawdzanie ,,negatywnego'' \(b\). Wtedy odległość między pozytywnymi kolejnymi \(b\) jest co najmniej \(2w\), gdzie \(w \le k\) jest liczbą sprawdzanych na lewo symboli \(a\). Zatem ,,lokalnie'' przesunięcie jest co najmniej dwukrotnie większe niż liczba dodatkowych operacji.

Suma przesunięć wzorca na tekście \(y\) wynosi co najwyżej \(n\), sumaryczna liczba dodatkowych operacji jest więc co najwyżej \(\frac{1}{2}n\), a liczba wszystkich operacji nie przekracza \(\frac{3}{2}n\).

Dla tekstu \(w\;=\;(a^kba^k)^r\) i wzorca \(a^kba^k\) algorytm wykonuje okolo \(\frac{3}{2}|w|\) porównań,
w granicy, gdy \(k,r \rightarrow \infty \) otrzymujemy współczynnik \(\frac{3}{2}\) .

Obliczanie Tablicy Silnych Prefikso-Sufiksów

Algorytm liczenia silnych prefikso-sufiksów bazuje na następującej relacji między \(P\) a \(P'\):
$$(t=P[j]\ \textrm{oraz}\ x[t+1]\neq x[j+1])\ \Rightarrow\ P'[j]=t$$

$$(t=P[j],\ t\ge 0,\ \textrm{oraz}\ x[t+1]= x[j+1])\ \Rightarrow\ P'[j]=P'[t]$$

Nie musimy obliczać tablicy \(P\); potrzebna jest jedynie ostatnia wartość \(t=P[j]\), którą obliczamy on-line.

Pp[0] := -1;
t := -1;
for j := 1 to m do begin
    while (t >= 0) and (x[t+1] <> x[j]) do
        t := Pp[t];
    t := t+1;
    if (j = m) or (x[t+1] <> x[j+1]) then
        Pp[j] := t
    else
        Pp[j] := Pp[t];
end;

Gdy weźmiemy \(x\ =\ aba^{m-2}\) to \(P'[0]=-1\), \(P'[1]=0\), \(P'[2]=-1\), oraz dla \(3\leq j\leq m\) zachodzi \(P'[j]=1\). Jest to jest pesymistyczny przypadek dla algorytmu Silne Prefikso-Sufiksy, algorytm wykonuje wtedy \(3m-5\) porównań symboli.

Załóżmy, że alfabet jest liniowo uporządkowany. Pokażemy, że porównywanie symboli w sensie porządku liniowego można istotnie wykorzystać w algorytmach tekstowych. Porządek liniowy na symbolach implikuje porządek leksykograficzny na słowach, na przykład:
$$ab < ababab < abb < abbaa < abbaaaaaaaaaaa < abbaaaaaab$$

String-matching w pamięci stałej dla specjalnych wzorów

Oznaczmy przez \(MaxSuf(w)\) maksymalny leksykograficznie sufiks słowa \(w\). Słowo \(x\) nazwiemy specjalnym gdy \(MaxSuf(x)=x\).

Dlaczego słowa o tej własności są interesujące? Większość szybkich algorytmów szukania podsłów korzysta z okresów \(p\) prefiksów słowa. Liczenie tych okresów w ogólnym przypadku jest ,,wąskim gardłem'' w projekcie algorytmu. Natomiast dla słów specjalnych liczenie okresów jest trywialne.

Jeśli \(x\) jest specjalny to okres każdego prefiksu słowa \(x\) można policzyć następującym naiwnym algorytmem.

period := 1;
for i := 2 to j do
    if x[i] <> x[i - period] then
        period := i;
return period;

Funkcja Naiwne-Liczenie-Okresu daje zły wynik dla tekstów które nie są specjalne, na przykład załóżmy że \(x= (aba)^6a = abaabaabaabaabaabaa\). Wtedy kolejne wartości okresów dla pozycji \(j=1,\, 2,\, \ldots\) są:

a	b	a	a	b	a	a	b	a	a	b	a	a	b	a	a	b	a	a
1	2	2	4	5	5	7	8	8	10	11	11	13	14	14	16	17	17	19

Zatem Naiwne-Liczenie-Okresu(19) = 19, dla \(x = (aba)^6a\), wynik całkowicie niepoprawny.

Opiszemy teraz program szukający wzorca \(x\) w słowie \(y\) zakładając, że \(x\) jest specjalne. Program wczytuje dwa słowa, pierwsze z nich jest specjalne: \(x\) pamiętamy w tablicy \(x[0 \ldots m-1]\), \(y\) w tablicy \(y[0 \ldots n-1]\). Program wypisuje wszystkie wystąpienia \(x\) w \(y\), tzn. wszystkie takie pozycje \(i\), że \(y[i \ldots i+m-1] = x\). Zapisujemy szkielet programu w języku C++:

#include <iostream>
#include <string.h>
 
int i = 0, j = 0, p = 1;
 
void przesun() {
	if (j - 1 < 2 * p) {
		i = i + p;
		j = 0;
		p = 1;
	} else {
		j = j - p;
		i = i + p;
	}
}
 
int main() {
	std::string x, y;
	std::cin >> x >> y;
	int m = x.size(), n = y.size();
 
	while (i <= n - m) {
		if (j == m) {
			std::cout << i << "\n";
			przesun();
		} else if (x[j] == y[i + j]) {
			j = j + 1;
			if (x[j - 1] != x[j - 1 - p])
				p = j;
		} else {
			przesun();
		}
	}
}

Powyższy kod jest wstępem do programu szukającego dowolnego podsłowa, niekoniecznie będącego specjalnym. Podstawowym niezmiennikiem w programie przed każdym wykonaniem i po każdym zakończeniu pętli while jest:

1. \(x[0 \ldots j-1] = y[i \ldots i + j - 1]\),
2. Program wypisał wszystkie wcześniejsze wystąpienia \(i' < i\),
3. \(p\) jest okresem słowa \(x[0 \ldots j - 1]\).

Algorytm Specjalny-String-Matching działa w czasie liniowym, można to udowodnić obserwując zmiany wartości \(2i + j\). Zauważmy bowiem, że wartość ta nie zmniejsza się, a w wypadku pozytywnego testu (x[j] == y[i + j]) zwiększa się co najmniej o 1. Jednocześnie \(2i + j \leq 3n\).

String-matching w pamięci stałej dla dowolnych wzorców

Algorytm Specjalny-String-Matching można łatwo zmodyfikować tak, aby znajdował on wystąpienia dowolnego słowa (niekoniecznie specjalnego) w czasie liniowym i stałej pamięci. Niech \(x = uv\), gdzie \(v\) jest leksykograficzne maksymalnym sufiksem \(x\). Oznaczmy \(r=|u|\). Technicznie informacja o rozkładzie \(uv\) sprowadza się do pamiętania \(r\).

Własność rozkładu. Niech \(x=uv\) będzie rozkładem jak wyżej opisany. Wtedy słowo \(v\) występuje tylko raz w słowie \(uv\). Jeśli \(i' < i\) są początkami wystąpień \(v\) oraz \(i - i' < r\), to na pozycji \(i - 1\) nie kończy się wystąpienie \(u\).

Z powyższego faktu wynika stosunkowo prosty algorytm szukania \(x\) w czasie liniowym i pamięci stałej. Algorytm ten jest modyfikacją algorytmu Specjalny-String-Matching, w którym rolę \(x\) pełni \(v\).

Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.

W ten sposób pokazaliśmy, że problem szukania słowa \(x\) w słowie \(y\) można rozwiązać w czasie liniowym i pamięci (dodatkowej) stałej, jeśli znamy początkową pozycję \(r\) leksykograficznie maksymalnego sufiksu \(v\) słowa \(x\).

Liczenie maksymalnego sufiksu w pamięci stałej

W algorytmie szukania wzorca w pamięci stałej potrzebna jest pozycja \(r\), od której zaczyna się maksymalny sufiks. Pokażemy teraz, jak ją znajdować w czasie liniowym i w pamięci stałej. Kluczem do tego jest liczenie czegoś więcej: dla każdego prefiksu liczymy jego maksymalny sufiks, jak również dodatkowo jego okres.

To właśnie liczenie okresu daje efektywność, chociaż na końcu ten okres nie jest nam potrzebny. Przekształcimy najpierw algorytm Naiwne-Liczenie-Okresu na algorytm liczący długość najdłuższego specjalnego prefiksu włącznie z jego okresem.

period := 1;
for i := 2 to |x| do
    if x[i] < x[i - period] then
        period := i
    else if x[i] > x[i - period] then
        return (i-1, period);
return (|x|, period);

Skorzystamy z algorytmu Najdłuższy-Specjalny-Prefiks. Funkcja Maksymalny-Sufiks liczy początkową pozycję i okres maksymalnego sufiksu.

j := 1;
repeat
    (i, period) := Najdłuższy-Specjalny-Prefiks(x[j..n]);
    if i = n then
        return (j, period)
    else
        j := j + i - (i mod period);
forever;

Możemy przepisać algorytm Maksymalny-Sufiks tak, aby nie wywoływał on funkcji Najdłuższy-Specjalny-Prefiks, wpisując tę funkcję do algorytmu.

Arytmetyczna funkcja \(\bmod\) może być usunięta i zastąpiona przez operacje dodawania i odejmowania bez zmiany asymptotycznej złożoności. Algorytm Maksymalny-Sufiks wykonuje co najwyżej \(2|x|\) porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.

s := 1;
i := 2;
p := 1;
while i <= n do begin
    r := (i - s) mod p;
    if x[i] = x[s+r] then
        i := i + 1
    else if x[i] < x[s+r] then begin
        i := i + 1;
        p := i - s;
    end else begin
        s := i - r;
        i := s + 1;
        p := 1;
    end;
end;
return s;

Równoważność cykliczna słów

Rotacją słowa \(u = u[1\ldots n]\) jest każde słowo postaci \(u^{(k)} = u[k+1 \ldots n] u[1 \ldots k]\), w szczególności \(u^{(0)} = u^{(n)} = u\). Niech \(u,\, w\) będą słowami długości \(n\). Mówimy, że są one cyklicznie równoważne, gdy \(u^{(i)} = w^{(j)}\) dla pewnych \(i\), \(j\).

Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa \(u\) w słowie \(ww\), ale podamy algorytm znacznie prostszy, bazujący na liniowym porządku alfabetu. Algorytm ten będzie działał w czasie liniowym i w miejscu (dodatkowa pamięć jest stała). W algorytmie rozszerzamy tablice \(u\) i \(w\) na \(uu\) i \(ww\), ale robimy to jedynie dla uproszczenia - w rzeczywistości możemy poruszać się cyklicznie po \(u\) i po \(w\).

x := uu;
y := ww;
i := 0; j := 0;
while (i < n) and (j < n) do
	k := 1;
	while (x[i + k] = y[j + k]) do
		k := k + 1;
	if (k > n) then
		return true;
	if (x[i + k] > y[i + k]) then
		i := i + k
	else
		j := j + k;
end;
return false;

Zdefiniujmy:

\(D(u) = \lbrace k : 1 \leq k \leq n\) i \(u^{(k)} > w^{(j)}\) dla jakiegoś \(j\rbrace\),
\(D(w) = \lbrace k : 1 \leq k \leq n\) i \(w^{(k)} > u^{(j)}\) dla jakiegoś \(j\rbrace\).

Skorzystamy z prostego faktu:

Fakt.
Jeśli \(D(u) = [1 \ldots n]\) lub \(D(w) = [1 \ldots n]\), to \(u\) i \(w\) nie są równoważne cyklicznie. Uzasadnienie pozostawiamy jako ćwiczenie.

Poprawność algorytmu wynika teraz z tego, że po każdej iteracji głównej pętli zachodzi niezmiennik: \(D(w) \supseteq [1 \ldots i]\) oraz \(D(u)\supseteq [1 \ldots j]\). Liczba porównań symboli w algorytmie jest oczywiście liniowa. Pozostawiamy jako ćwiczenie policzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości \(n\).

Uwaga: Dla uproszczenia rozważamy tylko teksty binarne.

Uogólnienie pozostawiamy jako proste ćwiczenie.

Słowem (ciągiem) de Bruijna rzędu \(n\) jest ciąg binarny o długości \(2^{n}\), w którym (traktowanym jako ciąg cykliczny) każdy ciąg binarny długości \(n\) wystęuje dokładnie raz.

Zdefiniujmy pierwiastek pierwotny \(y\) jako najkrótszy prefiks \(z\) słowa \(y\) taki, że \(y\) jest naturalną potęgą \(z\).

Słowa Lyndona sa zwartymi reprezentacjami liniowymi słów cyklicznych. Dla słowa \(x\) niech \(y\) będzie minimalnym cyklicznym przesunięciem \(x\). Wtedy pierwiastek pierwotny \(z\) słowa \(y\) jest słowem Lyndona. Słowo jest ciągiem Lyndona wtedy i tylko wtedy, gdy może powstać w ten sposób.

Definicja równoważna: słowo jest Lyndona jeśli jest leksykograficznie najmniejsze ze swoich przesunięć cyklicznych (równoważnie, najmniejsze ze swoich sufiksów).

Dla danego \(n\) przez \(ext(x,\, n)\) oznaczmy rozszerzenie okresowe słowa \(x\) do długości \(n\), oraz przez \(LastZero(x)\) oznaczamy najdłuższy prefiks słowa \(x\) kończący się zerem. Na przykład
$$ext(00111,\, 13) = 00111\;00111\;001, \quad LastZero(0010111)=0010.$$

Następujący algorytm generuje wszytkie słowa Lyndona o długości co najwyżej \(n\):

x := '0';
writeln(x);
while x != '1' do begin
	x := LastZero(ext(x, n));
	Zamień ostatni symbol x na jedynkę;
	writeln(x);
end;

Niech \( L_0 < L_1 < L_2 < \ldots < L_s \) będzie leksykograficznie posortowaną sekwencją wszystkich binarnych słów Lyndona o długości będącej dzielnikiem \(n\). Niech \(\mathcal{L}_n\) oznacza konkatenację
$$\mathcal{L}_n\ = \ L_0\cdot L_1\cdot L_2\cdot L_3 \cdot \ldots \cdot L_s$$

Przykład: Dla \(n=4\) algorym FM wygeneruje:
$$0 \quad 0001 \quad 001 \quad 0011 \quad 01 \quad 011 \quad 0111 \quad 1 $$
$$\mathcal{L}_4 = 0 \quad 0001 \quad 0011 \quad 01 \quad 0111 \quad 1 $$

Powiemy, że \(L_k\) jest "małe" gdy \(|L_k| < n\), w przeciwnym przypadku jest "duże". Z poprawności algorytmu FM (Fredricksena-Maiorany) wynikają własności:

• \(L_0=0,\ L_1=0^{n-1}1,\ L_{s-1}=01^{n-1},\ L_s=1\);
• jeśli \(L_k=\beta\alpha\) oraz \(\alpha\) zawiera zero, to \(\beta\) jest prefiksem \(L_{k+1}\)
• Jeśli \(L_k\) jest małe i \(k > 0\) to
  • \(L_{k-1}\) jest duże;
  • \(L_{k-1}\) kończy się co najmniej \(n - \vert L_k \vert \) jedynkami;
  • \(L_{k-1}\) jest bezpośrednio wygenerowane przed \(L_k\) w algorytmie FM.

Twierdzenie Fredricksena-Maiorany (dla pierwszych \(n\))

Przypadek szczególny - rozgrzewka: jeśli \(n\) jest liczbą pierwszą, to \(\mathcal{L}_n\) zawiera (cyklicznie) każde binarne słowo \(x\) długości \(n\).

Dowód

Przeprowadźmy dowód rozpatrując kilka przypadków.
Przypadek 1.
Niech \(x \in 1^*0^*\). Wtedy \(x\) jest podsłowem \(L_{s-1}L_sL_0L_1 = 01^n0^n1\). Załóżmy zatem (do końca dowodu), że nie zachodzi przypadek 1. Słowo \(x\) jest cyklicznie równoważne pewnemu słowu \(L_r\) (równemu minimalnemu cyklicznemu przesunięciu \(x\)). Wtedy dla pewnych \(\alpha\), \(\beta\)
$$x=\alpha\beta, \quad L_r=\beta\alpha $$
Ustalmy do końca dowodu \(\alpha\) i \(\beta\).

Przypadek 2.
\(\alpha\) zawiera zero. Wtedy \(\beta\) jest prefiksem \(L_{r+1}\), zatem \(x\) jest podsłowem \(L_rL_{r+1}\), którego prefiksem jest \(\beta\alpha\beta\).

Przypadek 3.
\(\alpha\in 1^+\). Załóżmy, że nie zachodzi przypadek 2. Wtedy \(\beta \notin 0^+\). Istnieje zatem taki indeks \(k\), że \(\beta\) jest prefiksem \(L_k\), ale \(\beta\) nie jest prefiksem \(L_{k-1}\). Niech \(\gamma\) będzie prefiksem \(L_{k-1}\) o długości \(\beta\). Zapiszmy \(L_{k-1} = \gamma\delta\). Udowodnimy:

Fakt: \(\delta \in 1^+.\) Dowód nie wprost. Przypuśćmy, że \(\delta\) zawiera 0, wtedy zgodnie z algorytmem Fredricksena-Maiorany następne leksykograficznie słowo Lyndona ma prefiks \(\gamma\). Wiemy, że \(\beta \neq \gamma\). Natomiast następnym słowem z definicji jest \(L_k\), które ma prefiks \(\beta\ne \gamma\), o tej samej długości co \(\gamma\). Sprzeczność.

Z powyższego faktu wynika, że \(\delta = \alpha\), ponieważ są to słowa tej samej długości składające się z samych jedynek. Zatem \(x\) jest podsłowem \(L_{k-1}L_k\) jako \(\delta\beta\), w konsekwencji \(x\) jest podsłowem całego słowa \(\mathcal{L}_n\). Koniec dowodu.

Twierdzenie Fredricksena-Maiorany (przypadek ogólny, dowolne \(n\))

\(\mathcal{L}_n\) zawiera (jako słowo cykliczne) każde binarne słowo \(x\) długości \(n\).

Dowód

Ponownie rozpatrujemy przypadki.

Przypadek 1: \(x \in 1^*0^*\). Dowód bez zmian (w stosunku do dowodu przypadku szczególnego). Załóżmy, zatem (do końca dowodu), że nie zachodzi przypadek 1. W przypadkach 2-4 zakładamy, że słowo \(x\) jest pierwotne. Zakładamy również, że \(x\) nie jest równe żadnemu \(L_r\). Wtedy \(x\) jest cyklicznie równoważne pewnemu słowu \(L_r\) (równemu minimalnemu cyklicznemu przesunięciu \(x\)). Wtedy dla pewnych niepustych \(\alpha,\, \beta\)
$$x=\alpha\beta,\ L_r=\beta\alpha$$

Niech \(L_k\) będzie leksykograficznie pierwszym dużym słowem o prefiksie \(\beta\).

Przypadek 2: \(\alpha \notin 1^+\). Dowód bez zmian.
Przypadek 3: \(\alpha\in 1^+\), \(L_{k-1}\) jest duże. Dowód bez zmian.
Przypadek 4: \(\alpha\in 1^+\), \(L_{k-1}\) jest małe.

Rozważamy podprzypadki A-C:
(A) \(|\beta| < |L_{k-1}|\). Wtedy \(L_{k-2}\) jest dużym słowem o prefiksie \(\beta\) co przeczy temu, że \(L_{k}\) jest najwcześniejsze. Zatem przypadek niemożliwy.
(B) \(L_{k-1}\) kończy się co najmniej \(|\alpha|\) jedynkami i \(\alpha\beta = x\) jest podsłowem \(L_{k-1}L_k\).
(C) \(L_{k-1}\) kończy się mniej niż \(|\alpha|\) jedynkami. Z definicji operacji okresowego rozszerzania wynika, że \(L_{k-1}\) jest okresem \(\beta\). Jednocześnie \(L_{k-2}\) (duże słowo) kończy się co najmniej \(n - |L_{k-1}|\geq |\alpha|\) jedynkami (gdyż \(|\beta|\geq |L_{k-1}|\) oraz \(|\alpha| = n - \beta|\)). Zatem \(\alpha\beta = x\) jest podsłowem \(L_{k-2}L_{k-1}L_k\).

Przypadek 5: Słowo \(x\) nie jest pierwotne. Wtedy dla pewnych \(k > 1\) oraz \(r,\, \alpha,\, \beta\) mamy \(x=(\alpha\beta)^k\), \(L_r=\beta\alpha\). Jeśli \(\alpha\notin 1^+\), to ponieważ słowo \(L_r\) jest małe i rozszerzenie okresowe zostaje zaburzone dopiero w ostatnim \(\alpha\) to \(L_{r+1}\) jest duże i ma prefiks \((\beta\alpha)^{k-1}\beta\). Zatem \(x\) jest podsłowem \(L_rL_{r+1}\).

Jeśli \(\alpha\in 1^+\) to \(L_{r-1}\) kończy się na \(\alpha\) (ma dostatecznie dużo jedynek), a ponieważ (z rozszerzenia okresowego) \(L_{r+1}\) ma prefiks \((\beta\alpha)^{k-1}\) to \(x\) jest podsłowem \(L_{r-1}L_rL_{r+1}\). Koniec dowodu.

Kilka wzorów

Niech zapisy \(Lyn(n),\ Pierw(n)\) oznaczają liczbę binarnych słów Lyndona oraz liczbę słów pierwotnych (nierozkładalnych) długości \(n\). Niech \(\mu\) będzie funkcją Möbiusa; spełnia ona wzór rekurencyjny:
$$\sum_{d | n} \mu(d) = [n=1].$$
Niech \(\phi\) będzie funkcją Eulera (ile jest liczb mniejszych od \(n\) względnie pierwszych z \(n\)). Przyjmujemy \(\phi(1)=1\). Użytecznym narzędziem kombinatorycznym jest formuła Möbiusa:
$$\forall_n\ f(n) = \sum_{d | n} g(d) \Rightarrow \forall_n\ g(n) = \sum_{d | n} \mu\left(\frac{n}{d}\right)f(d)$$
Mamy też wzory:
$$2^n = \sum_{d | n} Pierw(d),\quad n = \sum_{d | n} \phi(d).$$

Z formuły inwersyjnej Möbiusa i powyższego wzoru wynikają wzory:
$$Pierw(n) = \sum_{d | n}\mu\left(\frac{n}{d}\right) 2^d, \quad Lyn(n) = \frac{1}{n} \sum_{d | n}\mu\left(\frac{n}{d}\right) 2^d $$
Jeśli \(\mathcal{L}_n = L_0\cdot L_1\cdot L_2\cdot L_3 \ldots L_s\) jest rozkładem na słowa Lyndona o długości dzielącej \(n\) to oznaczmy \(||\mathcal{L}_n|| = s+1\). Inaczej mówiąc \(||\mathcal{L}_n||\) jest liczbą słów długości \(n\) cyklicznie nierównoważnych (liczba naszyjników binarnych z dokładnością do obrotu). Korzystając z poprzednich wzorów można udowodnić, że:
$$||\mathcal{L}_n|| = \frac{1}{n} \sum_{d | n} \phi\left(\frac{n}{d}\right)2^d.$$
Na przykład:
$$
\begin{gather}
Lyn(6)=9,\; Lyn(3)=2,\; Lyn(2)=1,\; Lyn(1)=2 \\
\vert \mathcal{L}_6 \vert = Lyn(1)+Lyn(2)+Lyn(3)+Lyn(6) = 14 \\
\vert \mathcal{L}_6 \vert = \frac{1}{6}
\left( \phi(1)\cdot 2^6+\phi(2)\cdot 2^3+\phi(3)\cdot 2^2+\phi(6)\cdot 2^1
\right) = \frac{1}{6}\left(1\cdot 2^6+1\cdot 2^3+2\cdot 2^2+2\cdot 2^1 \right)
\\
\end{gather}
$$

Słuszność tych wzorów można prześledzić na przykładzie:
$$
\begin{gather}
\mathcal{L}_6 = 0\ 000001\ 000011\ 000101\ 000111\ 001\ 001011 \
001101\ 001111\ 01\ 010111\ 011\ 011111\ 1
\end{gather}
$$

Teoriografowa metoda generacji ciągów de Bruijna

Chcemy wygenerować ciąg de Bruijna rzędu \(n\) nad alfabetem binarnym. Zbudujmy graf (tzw. graf de Bruijna rzędu \(n\)), którego wierzchołki etykietujemy wszystkimi możliwymi słowami binarnymi długości \(n\). Krawędzie etykietujemy symbolami z alfabetu i prowadzimy je według następującej reguły:

• Weź wierzchołek opisany \(n\)-znakową etykietą \(\alpha_1 \alpha_2 \ldots \alpha_n\).
• Poprowadź krawędź etykietowaną \(0\) do wierzchołka \(\alpha_2 \ldots \alpha_n 0\).
• Poprowadź krawędź etykietowaną \(1\) do wierzchołka \(\alpha_2 \ldots \alpha_n 1\).

Innymi słowy symbol na krawędzi jest dodawany od prawej strony do słowa reprezentowanego przez bieżący wierzchołek, spychając jednocześnie skrajnie lewy znak. Zatem przejście pewną sekwencją krawędzi \(v_1 \stackrel{c_1}{\to} v_2 \stackrel{c_2}{\to} v_3 \ldots v_k\) możemy utożsamić z wygenerowaniem ciągu znaków \(\alpha_1 \alpha_2 \ldots \alpha_n c_1 c_2 c_3 \ldots c_{k-1}\), gdzie oczywiście słowo \(\alpha_1 \ldots \alpha_n\) stanowi etykietę wierzchołka \(v_1\). Takie rozumowanie prowadzi wprost do rozwiązania problemu: w zbudowanym grafie odnajdujemy cykl Hamiltona, z którego bezpośrednio otrzymujemy ciąg de Bruijna. Ponieważ przejście cyklem Hamiltona odwiedzi każdy wierzchołek grafu, więc wygenerowany w ten sposób ciąg będzie zawierał jako podsłowo każde binarne słowo długości \(n\). Co prawda nie interesuje nas zawieranie każdego podsłowa w sensie dosłownym, lecz w sensie cykliczności ciągów de Bruijna, ale oznacza to, że w wynikowym ciągu wystarczy wyciąć \(n\) pierwszych albo ostatnich znaków. Przykład dla \(n = 3\) można zobaczyć na rysunku:

Niestety problem znajdowania cyklu Hamiltona jest NP-zupełny. Zauważmy jednak dwie istotne własności grafów de Bruijna:

1. Grafy de Bruijna posiadają cykl Eulera - do każdego wierzchołka wchodzi tyle samo krawędzi ile wychodzi z niego.
2. Weźmy graf de Bruijna rzędu \(n - 1\) i skonstruujmy dla niego tzw. graf krawędziowy (szczegóły poniżej). Otrzymamy w ten sposób graf de Bruijna rzędu \(n\).

Graf krawędziowy dowolnego grafu \(G\), to taki graf \(G'\), w którym wierzchołkami są krawędzie grafu \(G\), natomiast krawędziami jest relacja sąsiedztwa krawędzi w grafie \(G\). Tzn. jeśli dwie krawędzie w grafie \(G\) mają wspólny wierzchołek, to odpowiadające tym krawędziom wierzchołki w grafie \(G'\) połączone są krawędzią. Można łatwo pokazać, że cykl Eulera w pewnym grafie \(G\) ma jednoznaczne przełożenie na cykl Hamiltona w jego grafie krawędziowym \(G'\).

Z tego wynika, że możemy odnaleźć ciąg de Bruijna używając liniowego algorytmu znajdującego cykl Eulera w grafie rzędu mniejszego o jeden. Zatem dla \(n = 3\) operujemy na grafie de Bruijna rzędu \(2\). Przykład działania znajduje się na rysunku poniżej.

Zastosowanie ciągów de Bruijna do konstrukcji słów o dużej liczbie podsłów

Niech \(MaxSub(n)\) oznacza maksymalną liczbę różnych podsłów w słowie binarnym długości \(n\). Zachodzi:

Fakt.

$$\forall_{1\leq j\leq n}\ MaxSub(n) \leq 2^{j + 1} - 1 + \binom{n - j + 1}{2}$$

Uzasadnienie

Mamy co nawyżej \( 2^{j+1}-1\) podsłów binarnych długości co najwyżej \(j\), oraz co nawyżej \({n-j+1 \choose 2}\) podsłów długości co najmniej \(j+1\).

Wystarczy teraz znaleźć takie \(j\) dla którego zachodzo równość. Oznaczmy \(\gamma_k=2^k+k-1\). Zachodzi następujący fakt:

Fakt.

Jeśli \(\gamma_k < n \leq \gamma_{k+1}\) to \(MaxSub(n) \geq \; 2^{k+1} - 1 + \binom{n-k+1}{2}\).
Słowo osiągające maksymalną liczbę podsłów można skonstruować w czasie liniowym.

Uzasadnienie

Skonstruujemy słowo spełniające warunki:

1. wszystkie podsłowa długości \(k+1\) w \(\pi\) są parami różne, (w konsekwencji wszystkie podsłowa o większej lub równej długości też są różne, jest ich \(\binom{n - k + 1}{2}\)),
2. \(\pi\) zawiera wszystkie (czyli \(2^{k}\)) podsłowa binarne długości \(k\) (w konsekwencji wszystkie krótsze lub o tej samej długości słowa binarne, jest ich w sumie \(2^{k+1}-1\)).

Wtedy słowo \(\pi\) jest słowem długości \(n\) o maksymalnej liczbie podsłów, wynika to z poprzedniego faktu.

Konstrukcja słowa spełniającego powyższe warunki

Weźmy graf de Bruijna \(G\) rzędu \(k\) - wierzchołkami są wszystkie słowa binarne długości \(k\). Znajdujemy w nim ciąg \(\pi = a_1a_2 \ldots a_{n-k}\) będący ciągiem etykiet krawędzi pewnego cyklu spełniającego warunki:

1. cykl ten ma dokładnie \(n-k\) krawędzi w \(G\),
2. przechodzi przez każdą krawędź co najwyżej raz,
3. przechodzi przez każdy wierzchołek \(G\) co namniej jeden raz.

Pozostawiamy jako ćwiczenie dowód następującego faktu:

Ciekawy fakt teoriografowy.
Graf de Bruijna rzędu k posiada cykl \(\pi\) spełniający warunki (A-C) dla każdego \(\gamma_k < n \le \gamma_{k+1}\).

Uliniawiamy \(\pi\) dodając na końcu \(k\) początkowych liter \(\pi\), czyli słowo słowo \(a_1 a_2 \ldots a_k\). Słowo \(\pi\) ma teraz własności (1) i (2) i jest binarnym słowem długości \(n\) maksymalizującym liczbę podsłów.

Przykład

Dla \(n=14\) mamy \(k=3\), zaczynamy w wierzchołku \(000\) w grafie rzędu 3 a następnie konstruujemy cykl spełniający warunki (A-C) o długości \(n-k=11\), ciąg etykiet krawędzi cyklu to (patrz rysunek grafu):

$$\pi = 1\;0\;1\;1\;1\;1\;0\;1\;0\;0\;0$$

Dodajemy na końcu 3 początkowe litery i otrzymujemy wynik:

$$\pi = 1\;0\;1\;1\;1\;1\;0\;1\;0\;0\;0\;1\;0\;1$$

Ciąg ten jest binarnym słowem długości 14 o maksymalnej liczbie podsłów wynoszącej
$$2^{k+1} - 1 + \binom{n - k + 1}{2} = 2^4 - 1 + \binom{12}{2} = 15 + 6 \cdot 11 = 81.$$

Dwa słowa są kwadratowo równoważne gdy możemy zamienić jedno w drugie wykonując ciąg (być może pusty) operacji zamiany podsłowa typu \(zz\) przez \(z\) lub podsłowa \(z\) przez \(zz\). Inaczej mówiąc definiujemy \(z \approx zz\) oraz \(x \approx y\) gdy można otrzymać \(x\) z \(y\) przez wielokrotne stosowanie \(z \to zz\) dla podsłów \(x\) lub \(y\). Na przykład słowa abac, aabaabaac i ababaabaabbabbaacc są kwadratowo równoważne.

Niech \(\Sigma(x)\) będzie zbiorem liter słowa \(x\). Zauważmy, że
$$x\approx y\ \Rightarrow \ \Sigma(x)=\Sigma(y)$$

Oznaczamy
$$\hat{x} = p \alpha \beta q, \quad p,\, q \in \Sigma(x)^*, \ \alpha,\, \beta \in \Sigma(x)$$
gdzie \(p\alpha\) to najkrótszy prefiks taki, że \(\Sigma(p\alpha)=\Sigma(x)\) oraz \(\beta q\) najkrótszy sufiks o tej samej własności. Zauważmy, że
$$\Sigma(p) = \Sigma(x) - \lbrace \alpha \rbrace$$

Teoretyczna charakteryzacja równoważności kwadratowej.

Następujący fakt (a dokładniej punkt 2) daje algorytm sprawdzania równoważności kwadratowej.

Przy pomocy lematu udowodnijmy twierdzenie główne.

Konstrukcja efektywnego algorytmu

Korzystając wprost z twierdzenia można skontruować wykładniczy algorytm sprawdzania równoważności kwadratowej dwóch słów \(x_1\) i \(x_2\). Jeśli alfabet \( \Sigma \) jest stosunkowo niewielki, to można nieco inaczej podejść do problemu. Będziemy identyfikowali podsłowa słów \(x_1\) i \(x_2\) z pewnymi klasami abstrakcji relacji równoważności kwadratowej. Dzięki temu, znając identyfikatory podsłów \(p_1\), \(p_2\), \(s_1\) i \(s_2\) oraz symbole \(\alpha_1\), \(\alpha_2\), \(\beta_1\) i \(\beta_2\) będziemy mogli w czasie stałym odpowiedzieć na pytanie o równoważność kwadratową całych słów.

Dla ustalenia uwagi przyjmijmy, że działamy tylko na jednym słowie \(w = x_1 \$ x_2\) o długości \(n\). Dzięki temu gdy określimy klasę abstrakcji prefiksu \(x_1\) i sufiksu \(x_2\), będziemy mogli od razu odpowiedzieć na pytanie o równoważność kwadratową. Zauważmy bowiem, że słowo \(w\) ma rozkład \( (p,\, \alpha,\, \beta,\, s) = (x_1,\, \$,\, \$,\, x_2) \). Jednakże aby znaleźć identyfikator klasy abstrakcji słów \(x_1\) oraz \(x_2\), musimy dla nich wykonać odpowiedni rozkład, dla tych rozkładów wykonać kolejne itd. Każdy "poziom" rozkładu powoduje zmniejszenie rozmiaru alfabetu o 1. Skonstruujemy zatem algorytm bottom-up, który w kolejnych fazach \(k = 1,\, 2,\ldots,\, \vert \Sigma \vert \) będzie obliczał klasy abstrakcji podsłów, składających się z alfabetu rozmiaru \(k\).

Aby nie tracić czasu na częste odszukiwanie rozkładu \(p\) i \(s\) oraz odpowiadających im identyfikatorów klas abstrakcji, potrzebne nam będą dwie tablice. Niech \(PREF_k[i]\) zawiera identyfikator klasy abstrakcji podsłowa \(w[i..j]\), gdzie \(j\) jest takie, że podsłowo \(w[i..j]\) składa się z dokładnie \(k\) różnych znaków, ale podsłowo \(w[i..j+1]\) składa się już z \(k + 1\) różnych znaków. Zauważmy, że wtedy dla pewnego podsłowa \(v = w[i..t]\), gdzie \(t > j\) podsłowo \(w[i..j]\) jest \(p\) z twierdzenia, a symbol \(w[j+1]\) jest \(\alpha\) (przy założeniu lokalnego ograniczenia alfabetu do \(k + 1\) znaków). Niech także \(SUF_k[i]\) zawiera identyfikator klasy abstrakcji podsłowa \(w[j..i]\), gdzie \(j\) definiujemy analogicznie.

Dla \(k = 1\) ustalamy \(PREF_k[i] := SUF_k[i] := \mathcal{I}(w[i])\) dla \(i = 1,\, 2, \ldots,\, n\), gdzie \(\mathcal{I}\) jest operatorem nadania unikalnego identyfikatora symbolom z alfabetu \(\Sigma\). Dla \(k > 1\) obliczamy \(PREF_k\) następująco:

• Dla każdego \(i = 1,\, 2 \ldots\) szukamy wartości \(j\) (z definicji \(PREF\)).
• Obliczamy \(PREF_k[i]\) jako identyfikator klasy abstrakcji słowa reprezentowanego przez trójkę \( (PREF_{k-1}[i],\, \mathcal{I}(w[j + 1]),\, SUF_{k-1}[j]) \).

Analogicznie obliczamy \(SUF_k\). Dla ustalonego \(k\) algorytm działa w czasie liniowym: wartości \(j\) przy obliczaniu \(PREF\) (odpowiednio \(SUF\)) tylko rosną (odpowiednio maleją), więc ich wyznaczanie można wykonać w czasie liniowym. Drugą część również można wykonać liniowo; generujemy trójki zgodnie z algorytmem, a następnie sortujemy je pozycyjnie i bloki takich samych trójek numerujemy unikalnym identyfikatorem.

Podsumowując, powyższy algorytm dowodzi następującego faktu.

Twierdzenie

Równoważność kwadratową dwu tekstów o sumarycznym rozmiarze \(n\) nad alfabetem \(k\)-elementowym można sprawdzić w czasie \(O(n\cdot k)\).

Słowo jest powtórzeniem, gdy jest postaci \(zz\), gdzie \(z\) jest niepustym tekstem. Powtórzenia w tekstach reprezentują strukturę wewnętrznych okresowości i regularności, których wyszukiwanie ma zastosowania np. w biologii obliczeniowej. Powtórzenia są związane z kompresją tekstów. Im więcej powtórzeń w słowie, tym bardziej jest kompresowalne.

Powtarzające się segmenty tekstu związane są z kompresją. Jeśli mamy dwie kopie tego samego (być może długiego) podsłowa, to drugą z nich możemy zastąpić referencją do pierwszej. Jeśli czytamy tekst od lewej do prawej i napotkamy segment \(x[i..j]\), który pojawił się wcześniej jako \(x[p..q]\), gdzie \(q < i\), to możemy reprezentować \(x[i..j]\) przez parę liczb \([p,\, q]\). Filozofia ta prowadzi do rodziny algorytmów kompresji podanych przez Lempela i Ziva (kompresji typu LZ). Jest wiele różnych wariantów tego typu kompresji.

Zdefiniujmy teraz faktoryzację tekstów typu LZ. Faktoryzacją tekstu \(x\) jest rozkład \(x = v_{1}v_{2}\dots v_{m}\), gdzie \(v_1=x[1]\), oraz jeśli \(|v_1v_2 \dots v_{k-1}| = i-1\), to \(v_k\) jest najdłuższym tekstem, który występuje w \(v_1v_2 \dots v_{k-1}\), a jeśli takiego nie ma, to \(v_k=x[i]\).

Oznaczmy przez \(LZ(x)\) faktoryzację \(x\). Faktoryzacja taka nazywana jest czasem faktoryzacją Crochemora, który z niej korzystał przy szukaniu powtórzeń. Różni się ona jedynie kosmetycznie od faktoryzacji związanej bezpośrednio z algorytmem Lempel-Ziv. Dlatego też będziemy nazywać ją faktoryzacją LZ.

Korzystając z drzew sufiksowych można udowodnić następujący fakt:

Dla danego tekstu \(x\) długości \(n\) możemy policzyć \(LZ(x)\) w czasie liniowym. Zakładamy tutaj, że alfabet da się posortować w czasie liniowym (jest to naturalne założenie).

Powtórzenia zakotwiczone

Przypuśćmy, że \(x=uv\). Powtórzenie jest \((u,\, v)\)-zakotwiczone (na pozycji pomiędzy \(u\) i \(v\)), gdy zaczyna się w \(u\) i kończy w \(v\). Wprowadzimy dwie funkcje logiczne \(RightTest(u,\, v)\), i \(LeftTest(u,\, v)\) dla słów \(u,\, v\). \(RightTest(u,\, v)\) zachodzi, gdy istnieje \((u,\, v)\)-zakotwiczone powtórzenie, którego środek znajduje się na początku lub wewnątrz \(v\). Podobnie definiujemy \(LeftTest\) dla słowa \(u\).

Rozważmy przypadek obliczania \(RightTest\).

Dla każdej pozycji \(k\) w \(v\) liczymy

• \(PREF[k]\): długość maksymalnego podsłowa zaczynającego się w \(k\) i będącego prefiksem \(v\);
• \(S[k]\): długość maksymalnego podsłowa kończącego się na pozycji \(k-1\) i będącego sufiksem \(u\).

Własność funkcji \(RightTest\): \(RightTest(u,v)\) zachodzi wtedy i tylko wtedy, gdy dla pewnego \(k\) mamy nierówność \(PREF[k]+S[k] \geq k\), patrz rysunek.

Wiemy już jak obliczyć tablicę \(PREF\) w czasie liniowym, tablicę \(S\) liczymy symetrycznie. W ten sposób pokazaliśmy, że obliczenie \(RightTest(u,\, v)\) wymaga jedynie czasu liniowego. Podobnie jest dla \(LeftTest\).

Szukanie dowolnych powtórzeń w czasie \(n \log n\)

Niech \(Test(u,\, v)\) będzie funkcją logiczną wyrażającą fakt posiadania przez \(x\) powtórzenia \((u,\, v)\)-zakotwiczonego. Inaczej mówiąc, \(Test(u,\, v) \equiv RightTest(u,\, v)\ \textrm{lub}\ LeftTest(u,\, v)\). Następujący algorytm ma strukturę taką, jak merge-sort. Szukamy powtórzenia w lewej połowie, w prawej oraz na styku obu połówek (funkcja \(Test\)).

Algorytm w oczywisty sposób działa w czasie \(O(n \log n)\), gdyż liczenie funkcji \(Test\) jest w czasie liniowym.

Dygresja: Istnieje ciekawa wersja tego algorytmu, działająca w czasie \(O(n \log n)\) i (dodatkowej) pamięci stałej (nie możemy mieć dodatkowych tablic \(PREF,\ S\)).

Szukanie dowolnych powtórzeń w czasie liniowym

Algorytm liniowy szukania powtórzenia opiera się na faktoryzacji tekstów. Niech
$$LZ(x) = (v_{1},\, v_{2},\, \ldots,\, v_{m})$$

\(x\) zawiera powtórzenie wtedy i tylko wtedy, gdy dla pewnego \(k\) zachodzi
$$RightTest(v_1\, v_2\, \ldots\, v_{k-2},\, v_{k-1}\, v_k) \ \mathrm{lub}\ RightTest(v_1\, v_2\, \ldots\, v_{k-1},\, v_k)$$

Dowód tej własności pozostawiamy jako ćwiczenie.

Algorytm działa w czasie liniowym, pozostawiamy to jako ćwiczenie.

Oznaczmy przez \(Subwords(x)\) wszystkie podsłowa tekstu \(x\), a wszystkie wystąpienia (początkowe pozycje) słowa \(z\) w słowie \(x\) oznaczmy przez \(Occ(z,\, x)\). Oznaczenie \(Occ\) jest skrótem od ang. occurrences. Chcemy znaleźć taką reprezentację zbioru \(Subwords(x)\), by można było łatwo odpowiedzieć na pytanie, czy \(z \in Subwords(x)\), co jest równoważne \(Occ(z,\, x) \neq \emptyset\), jak również rozwiązywać inne problemy tekstowe. Poza tym chcemy, by rozmiar tej reprezentacji był liniowy, podczas gdy rozmiar \(Subwords(x)\) może być kwadratowy. Spośród wielu dobrych reprezentacji najprostszymi są tablice sufiksowe (oznaczane przez \(SA\) - suffix array).

Niech \(x = a_{1}a_{2}\dots a_{n}\) i niech \(x_{n+1}=\#\) będzie specjalnym znakiem leksykograficznie większym od każdego innego symbolu (czasami będziemy również używać \(x_{n+1}=\#\) jako najmniejszego leksykograficznie symbolu). Oznaczmy przez \(sufiks_{i}=a_{i}a_{i+1}\dots a_{n}\) sufiks tekstu \(x\) zaczynający się na pozycji \(i\)-tej. Niech \(SA[k]\) będzie pozycją, od której zaczyna się \(k\)-ty leksykograficznie sufiks \(x\). Sufiks zaczynający się na pozycji \((n+1)\)-szej nie jest brany pod uwagę. Ciąg sufiksów posortowany leksykograficznie wygląda następująco:

$$sufiks_{SA[1]} < sufiks_{SA[2]} < sufiks_{SA[3]} < \ldots < sufiks_{SA[n]}$$

Przykład.
Rozważmy tablicę sufiksową \(SA_n\) dla n-tego słowa Thue-Morse'a:
$$\tau_0=0,\ \tau_1=01,\ \tau_2=0110,\ \tau_3=01101001.$$
$$SA_1 = 0\;1,\, SA_2 = 3\;0\;2\;1,\, SA_3 = 5\;6\;3\;0\;7\;4\;2\;1$$

Dla parzystych \(n\) konstruujemy tablicę z poprzedniej następująco.

Załóżmy, że \(SA_{n-1}\) składa się z połówek \(\alpha,\, \beta\). Wtedy
$$SA_n = (2\beta + 1,\, 2\alpha,\, 2\beta,\, 2\alpha+1).$$
Dla nieparzystych \(n\) robimy poprawkę: początek drugiej ćwiartki przenosimy na pozycję \(p(n)+1\), a początek ostatniej ćwiartki przenosimy na początek trzeciej ćwiartki.

Liczby \(p(n)\) zadane są poprzez
$$p(3)=1,\ p(n+2)=4 \cdot p(n)+1.$$
Równoważnie
$$p(2n+1) = (4^n-1)/3+1.$$

Zamiast tablicy SA można wprowadzić tablice posortowanych cyklicznych przesunięć (pierwsze pozycje). Wtedy dla słów Thue-Morse'a tablice takie konstruujemy podobnie jak tablice SA, ale dużo prościej, nie jest wymagana poprawka.

Przykład.
Jako drugi przykład rozważmy słowa Fibonacciego kończące się literą a. Niech \(N\) będzie długością słowa.

Dla tych słów tablica sufiksowa, jako ciąg, jest postępem arytmetycznym (modulo \(N\), numeracja pozycji zaczyna się od zera). Pierwszym elementem ciągu jest \(N-1\) (ostatnia pozycja - odpowiada to sufiksowi składającemu się z jednej litery a). Różnicą postępu arytmetycznego jest liczba Fibonacciego.

Dla słów Fibonacciego tablice przesunięć cyklicznych jako ciągi są postępami arytmetycznymi. Zachodzi następujący fakt:

Fakt.
Zbiór wystąpień dowolnego wzorca w słowie Fibonacciego (pierwsze pozycje) jest postępem arytmetycznym (modulo długość całego słowa).

Oznaczmy przez \(LCP[k]\) długość wspólnego prefiksu \(k\)-tego i następnego sufiksu w kolejności leksykograficznej. Tablica sufiksowa ma następującą przydatną własność. Niech
$$
\begin{split}
& first_{z} = \min \lbrace k : z \text{ jest prefiksem } sufiks_{SA[k]}\rbrace \\
& last_{z} = \max \lbrace k : z \text{ jest prefiksem } sufiks_{SA[k]}\rbrace \\
\end{split}
$$

Wtedy \(Occ(z,\, x)\) jest przedziałem w tablicy sufiksowej od \(first_{z}\) do \(last_{z}\).

Szukanie podsłów

Pokażemy, jak sprawdzać, czy \(z\) występuje w \(x\) używając w tym celu tablicy sufiksowej.

Możemy sprawdzić, czy \(z\) jest prefiksem \(i\)-tego sufiksu w czasie \(O(m)\). Korzystając z tego, wykonujemy rodzaj binarnego szukania. W ten sposób znajdujemy pierwszy sufiks, którego prefiksem jest \(z\). Jeśli jest taki sufiks, to \(z \in Subwords(x)\). W przeciwnym wypadku \(z\) nie jest podsłowem \(x\). Podobnie znajdujemy ostatni sufiks. Zbiór wystąpień odpowiada przedziałowi w tablicy \(SA\) między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od \(z\). Złożoność czasowa algorytmu wynosi \(O(m \log n)\).

Wyznaczanie liczby podsłów

Pokażemy, jak znaleźć liczbę podsłów słowa \(x\) przy pomocy tablicy sufiksowej. Końcowego znacznika \(\#\) nie traktujemy jako części słowa \(x\). Liczba podsłów jest równa \(\vert Subwords(x) \vert \). Jeśli wszystkie symbole słowa są różne to oczywiście \(\vert Subwords(x) \vert = \binom{n + 1}{2}\). W przeciwnym wypadku liczymy
$$\binom{n+1}{2} - \sum_i LCP[i]$$

Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona. Mając tablicę sufiksową oraz LCP algorytm działa oczywiście w czasie \(O(n)\).

Podobnie jak tablicę sufiksową możemy zdefiniować tablicę \(ROT\), odpowiadającą posortowanemu ciągowi wszystkich cyklicznych przesunięć słowa \(x\) (rotacji \(x\)). Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu obliczania tablicy \(ROT\), przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.

Dygresja. Ciekawą klasę słów, dla których tablice \(SA\) i \(ROT\) są szczególnie interesujące, stanowią słowa Fibonacciego \(Fib_n\). W tym szczególnym przypadku załóżmy, że pozycje numerujemy od zera. Dla każdego \(n\) tablica \(ROT\) jest postępem arytmetycznym (modulo długość słowa). Natomiast tablica \(SA\) jest postępem arytmetycznym, gdy \(n\) jest parzyste. Ciekawym ćwiczeniem jest znalezienie wzoru na \(\vert Subwords(Fib_n)\vert\).

Obliczanie tablicy \(LCP\)

Niech \(rank(i)\) będzie pozycją \(sufiks_i\) w porządku leksykograficznym. W naszym przykładowym słowie mamy:
$$ rank = [8,\, 2,\, 7,\, 1,\, 3,\, 9,\, 4,\, 10,\, 5,\, 12,\, 11,\, 6] $$

Niech \(LCP'[k] = LCP[rank[k]-1]\). Załóżmy dla uproszczenia, że \(LCP[0] = 0\) oraz że tekst kończy się specjalnym symbolem. Obliczamy tablice \(LCP',\, LCP\) następująco:

for i := 1 to n do
    rank[SA[i]] := i;
l := 0;
for i := 1 to n do
begin
    if (rank[i] > 1) then
        while (x[l + i] = x[l + SA[rank[i] - 1]]) do
            l := l + 1;
    LCPp[i] := l;
    if (l > 0) then
        l := l - 1;
end;

Pozostawiamy jako ćwiczenie dowód tego, że
$$ LCP'[k] \geq LCP'[k-1]-1$$.

Jeśli \(LCP'[k-1] - 1 = t\), to \(LCP'[k]\) obliczamy sprawdzając symbol po symbolu (od lewej do prawej) zgodność prefiksów odpowiednich słów startując od pozycji \(t\). W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potem idziemy "do przodu" (sprawdzając kolejne symbole). Jest to analiza typu "jeden krok do tyłu i kilka do przodu". Liczba iteracji jest liniowa, więc liczba kroków do tyłu też. Ponieważ odległość "do celu" jest liniowa, to suma kroków też jest liniowa.

Słownik podsłów bazowych i konstrukcja tablicy sufiksowej w czasie \(O(n \log n)\)

Opiszemy uproszczoną wersję algorytmu Karpa-Millera-Rosenberga (w skrócie algorytmu KMR) rozwiązywania problemów tekstowych metodą słownika podsłów bazowych. Ustalmy pewien tekst \(x\) długości \(n\). Zakładamy w tej sekcji, że dodatkowym symbolem jest \(x_{n+1}=\#\), leksykograficznie największy symbol. Przez segment \(k\)-bazowy rozumiemy segment tekstu \(x[i .. i+2^k-1]\) długości \(2^k\) lub kończący się na \(x_{n+1}\). W praktyce programistycznej możemy przyjąć, że po symbolu \(\#\) mamy bardzo dużo takich symboli na prawo i każdy segment startujący w \(x[1 .. n]\) ma dokładnie długość \(2^k\).

Słownik podsłów bazowych słowa \(x\) (w skrócie \(DBF(x)\), od ang. dictionary of basic factors) składa się z \(\log n\) tablic \(DBF_0\), \(DBF_1\), \(DBF_2\), \( \ldots DBF_{\left\lceil \log n \right\rceil}\). Przyjmujemy, że \(DBF_k[i]\) jest pozycją słowa \(x[i..i+2^k-1]\) na posortowanej liście (bez powtórzeń) wszystkich podsłów długości \(2^k\) słowa \(x\). Jeśli długość "wystaje" poza koniec \(x\) to przyjmujemy, że są tam (umownie) same symbole \(\#\).

Algorytm liczenia tablic \(DBF\) jest bardzo prosty. Załóżmy od razu, że symbole są ponumerowane leksykograficznie. Wtedy \(DBF_0\) jest zasadniczo równa tekstowi \(x\). Wyznaczamy \(DBF_{k+1}\) na podstawie \(DBF_k\) w następujący sposób. Dla każdego \(i\) tworzymy nazwę-kompozycję słowa \(x[i..i+2^{k+1}-1]\) jako parę liczb naturalnych \((DBF_k[i],\, DBF_k[i+2^k])\). Sortujemy te pary w czasie liniowym algorytmem sortowania pozycyjnego (RadixSort) i w ten sposób otrzymujemy tablicę, która koduje (w porządku leksykograficznym) każdą parę liczbą naturalną (pozycją w porządku leksykograficznym). Wartością \(DBF_{k+1}[i]\) jest kod pary \((DBF_k[i],\, DBF_k[i+2^k])\).

Zauważmy, że tablica sufiksowa odpowiada tablicy \(DBF_{\lceil \log n \rceil}\). Możemy to podsumować następująco:

• Słownik \(DBF(x)\) możemy skonstruować w czasie \( O(n \log n) \) i pamięci \(O(n \log n)\) (jest to również rozmiar słownika).
• Tablicę sufiksową możemy otrzymać, stosując algorytm KMR, w czasie \(O(n \log n)\) i pamięci \(O(n)\) (potrzebujemy pamiętać jedynie ostatnie dwa wiersze tablicy \(DBF\) w każdej iteracji).

Konstrukcja tablicy \(SA\) w czasie \(O(n)\): algorytm KS

Opiszemy teraz błyskotliwy algorytm Kärkkäinena-Sandersa (w skrócie KS), będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR oblicza znacznie więcej niż tablica sufiksowa, ponieważ konstruuje słownik podsłów bazowych wielkości \(n \log n\) (mający liczne inne zastosowania, ale jako całość być może niepotrzebny przy liczeniu tablicy sufiksowej).

Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozbijmy zbiór pozycji \([1..n]\) tekstu \(x\) na dwa zbiory \(N\), \(M\):

• Zbiór \(N\) zawiera co trzecią pozycję w tekście: \(N = \lbrace 3,\, 6,\, 9,\, 12,\, 15 \ldots \rbrace\)
• Zbiór \(M\) zawiera pozostałe pozycje: \(M = \lbrace 1,\, 2,\, 4,\, 5,\, 7,\, 8,\, 10,\, 11 \ldots \rbrace\)

Przez \(SA_M\), oznaczmy tablicę sufiksową dla pozycji ze zbioru \(M\), podobnie zdefiniujmy \(SA_N\). \(SA_M\) daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru \(M\).

Sprowadzenie obliczania \(SA_M\) do obliczania tablicy sufiksowej rozmiaru \(\frac{2}{3}n\)

Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie \(x\) korzystając z RadixSort. Każdemu takiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy \(kod(z)\) otrzymaną nazwę podsłowa długości 3. Zakładamy, że \(x\) kończy się dodatkowo dwoma symbolami \(\#\), ale rozważamy tylko podsłowa zaczynające się w \(x\). Dla uproszczenia załóżmy, że 3 jest dzielnikiem \(n\).

Tworzymy nowe słowo \(compress(x)\) w następujący sposób:

$$
\begin{split}
& y1 = kod(a_1 a_2 a_3) \cdot kod(a_4 a_5 a_6) \ldots kod(a_{n-2} a_{n-1} a_n) \\
& y2 = kod(a_2 a_3 a_4) \cdot kod(a_5 a_6 a_7) \ldots kod(a_{n-1} a_{n} a_{n+1}) \\
\end{split}
$$

$$compress(x) = y1 \; \& \; y2$$
gdzie \(\&\) jest nowym maksymalnym symbolem.

Jeśli mamy tablicę sufiksową dla słowa \(compress(x)\), można łatwo obliczyć \(SA_M\) w czasie liniowym. Pozostawiamy to jako ćwiczenie.

Krok 1. algorytmu sprowadza się do RadixSort, podobnie jak w algorytmie KMR. Kroki 3. i 4. są proste i ich implementację pozostawiamy Czytelnikowi jako ćwiczenie. Najważniejszy jest krok scalania. Mamy dwie posortowane listy sufiksów i trzeba je scalić w jedną posortowaną listę. Zasadniczym problemem jest implementacja operacji porównania leksykograficznego dwóch (długich) sufiksów w czasie stałym.

Jeśli oba sufiksy są typu \(M\) lub oba są typu \(N\), to porównanie jest w czasie stałym, bo mamy posortowane listy takich sufiksów. Jeśli nie, to mamy dwa przypadki.

Przypadek 1.
Mamy sufiks typu \(M\) na pozycji \(i \bmod 3 = 1\) oraz pewien sufiks typu \(N\) na pozycji \(j\). Porównujemy ze sobą pary \((x[i],\, sufiks_{i+1})\) i \((x[j],\, sufiks_{j+1})\). Ponieważ \(i + 1 \bmod 3 = 2\) i \(j + 1 \bmod 3 = 1\), to oba te sufiksy są typu \(M\), zatem można je porównać w czasie stałym.

Przypadek 2.
Mamy sufiks typu \(M\) na pozycji \(i \bmod 3 = 2\) oraz pewien sufiks typu \(N\) na pozycji \(j\). Tym razem porównujemy trójki \((x[i],\, x[i+1],\, sufiks_{i+2})\) i \((x[j],\, x[j+1],\, sufiks_{j+2})\). Ponieważ \(i + 2 \bmod 3 = 1\) i \(j + 2 \bmod 3 = 2\), to oba te sufiksy są typu \(M\), zatem można je porównać w czasie stałym.

Niech \(T(n)\) będzie czasem działania algorytmu KS. Zachodzi
$$T\left (n \right) = T \left( \left\lceil \frac{2}{3}\cdot n \right\rceil \right) + O\left( n \right).$$
Rozwiązaniem jest \(T(n) = O(n)\). Mamy więc liniowy algorytm liczenia tablicy sufiksowej.

Dużo starszym od tablic sufiksowych pomysłem na reprezentację wszystkich podsłów tekstu jest struktura drzewa sufiksowego. Drzewo sufiksowe jest drzewem TRIE zbudowanym z wszystkich sufiksów danego tekstu. Dla przypomnienia: TRIE to drzewo, w którym każda krawędź jest etykietowana pewnym znakiem lub ciągiem znaków. Wtedy korzeń TRIE reprezentuje napis pusty, natomiast ścieżki od korzenia do dowolnego innego węzła w drzewie reprezentują pewien napis, zbudowany z konkatenacji etykiet na krawędziach tworzących tę ścieżkę. Ponieważ zgodnie z definicją drzewo sufiksowe budujemy z wszystkich sufiksów tekstu, otrzymujemy strukturę danych reprezentującą wszystkie podsłowa. Na początku skupimy się na zastosowaniach drzewa sufiksowego, następnie na algorytmach jego konstrukcji.

W poniższych rozważaniach zakładamy, że budujemy drzewo sufiksowe z tekstu postaci \(x\#\), gdzie \(\#\) jest specjalnym symbolem niewystępującym w alfabecie. Oznacza to, że każdemu sufiksowi słowa \(x\) odpowiada w drzewie sufiksowym dokładnie jeden liść. Ułatwi to nieco rozważania teoretyczne, natomiast w praktyce nie jest taki sposób konstrukcji drzewa niezbędny.

Szukanie podsłów

Aby sprawdzić, czy w zadanym tekście występuje jakiś wzorzec \(y = y_1 y_2 \ldots y_m \) próbujemy zbudować w drzewie sufiksowym ścieżkę rozpoczynającą się w korzeniu i przechodzącą kolejno krawędziami etykietowanymi znakami \(y_1\), \(y_2\) itd. Jeśli w pewnym momencie po zbudowaniu ścieżki składającej się z pierwszych \(i\) symboli słowa \(y\) nie możemy przejść do symbolu \(y_{i+1}\), ponieważ w drzewie nie istnieje krawędź o odpowiedniej etykiecie, to znaczy, że słowo \(y\) nie występuje w tekście \(x\).

Jeśli jednak zbudujemy całą ścieżkę i znajdziemy się na końcu w pewnym punkcie drzewa sufiksowego, możemy łatwo znaleźć wartości takie, jak liczba i miejsca wystąpień wzorca \(y\) w tekście \(x\). Zbiór wystąpień bowiem można łatwo określić patrząc na liście poddrzewa ukorzenionego w punkcie, w którym skończyliśmy wyszukiwane wzorca. Ponieważ istnieje odpowiedniość pomiędzy liścmi drzewa i sufiksami tekstu, łatwo można określić zbiór pozycji, na których wzorzec występuje. Oczywiście można dzięki temu znaleźć także np. pierwsze czy ostatnie wystąpienie dowolnego wzorca w tekście.

Zadanie: Jak znaleźć najdłuższe podsłowo występujące przynajmniej 2 razy w tekście? Jak zmieni się algorytm, jeśli będziemy szukać podsłów występujących co najmniej (albo dokładnie) \(k\) razy w tekście?

Wyznaczanie liczby podsłów

Napisaliśmy wcześniej, że krawędź w TRIE jest etykietowana znakiem lub ciągiem znaków. Zdefiniujmy wagę krawędzi jako liczbę znaków, które znajdują się na etykiecie. Wtedy liczbę różnych podsłów w danym tekście można obliczyć sumując wagi wszystkich krawędzi drzewa sufiksowego.

Konstrukcja drzewa sufiksowego

W oczywisty sposób możemy zbudować drzewo sufiksowe w czasie \(O(n^2)\) poprzez dodawanie do TRIE kolejnych sufiksów tekstu (zarówno tutaj jak i w dalszej części zakładamy, że alfabet \(\Sigma\) ma rozmiar stały; w przeciwnym przypadku do każdej operacji należy dodać czynnik \(\log \vert \Sigma \vert\)). Wtedy każda krawędź drzewa jest etykietowana pojedynczym znakiem. Rozmiar takiej struktury danych także jest kwadratowy. Aby w ogóle rozważać szybszy algorytm konstrukcji struktury danych, należy określić taką jej reprezentację, której rozmiar jest mniejszy niż kwadratowy względem rozmiaru danych.

Zmieńmy nieco podejście: jeśli w drzewie występuje łańcuch krawędzi bez żadnych rozgałęzień, to zastępujemy go pojedynczą krawędzią etykietowaną kolejnymi znakami z zastępowanego właśnie łańcucha. Będziemy o takiej strukturze mówić skompresowane drzewo sufiksowe. Zauważmy, że ponieważ skompresowane drzewo ma dokładnie \(n + 1\) liści (dla tekstu postaci \(x = x_1 x_2 \ldots x_n \#\)), to ma dokładnie \(n\) węzłów wewnętrznych, a zatem \(2n\) krawędzi. Co więcej, krawędzi nie musimy etykietować explicite ciągiem znaków, lecz parą liczb, oznaczających początek i koniec pewnego podsłowa w tekście \(x\). Otrzymaliśmy w ten sposób reprezentację drzewa sufiksowego liniowego rozmiaru.

W wyniku kompresji przestają istnieć niektóre węzły drzewa, do których mimo wszystko będziemy się odnosić w dalszej części tekstu. Takie wierzchołki będziemy nazywać niejawnymi, natomiast wierzchołki rzeczywiście istniejące w skompresowanych drzewach sufiksowych nazwiemy jawnymi. Zdefiniujmy dodatkowo operację \(Label(v)\), która dla zadanego węzła \(v\) w drzewie generuje słowo z nim stowarzyszone oraz tzw. dowiązanie sufiksowe (ang. suffix link) \(Suf(v)\), które dla zadanego węzła \(v\) takiego, że \(Label(v) = y_0 y_1 y_2 \ldots y_k\) zwraca wskaźnik na taki węzeł \(v'\), że \(Label(v') = y_1 y_2 \ldots y_k\). Czyli innymi słowy otrzymujemy wskaźnik na węzeł reprezentujący słowo pozbawione pierwszego znaku. Dla korzenia \(root\), którego \(Label\) jest słowem pustym, przyjmujemy \(Suf(root) = root\).

Algorytm McCreighta - konstrukcja offline

Algorytm McCreighta buduje skompresowane drzewo sufiksowe w kolejności od najdłuższego sufiksu do najkrótszego. Ogólny schemat algorytmu jest następujący:

• W fazie pierwszej inicjujemy drzewo najdłuższym sufiksem \(sufiks_1\), czyli pojedynczą krawędzią reprezentującą cały tekst \(x\).
• Załóżmy, że jesteśmy w fazie \(k > 1\) i dodajemy do drzewa \(sufiks_k\).
• Przedstawmy słowo \(sufiks_k\) jako konkatenację dwóch słów \(p q\) takich, że słowo \(p\) jest najdłuższym prefiksem \(sufiks_k\), który można utworzyć podążając ścieżką od korzenia w dół drzewa. Taki rozkład jest jednoznaczny.
• Definiujemy głowę \(head_k\) \(k\)-tego sufiksu jako taki węzeł \(v\) (być może niejawny) w drzewie, że \(Label(v) = p\).
• Dodajemy do drzewa krawędź reprezentującą słowo \(q\) w węźle \(head_k\).

Dość łatwo można dostrzec analogię pomiędzy problemem znajdowania \(head_k\) a obliczaniem najdłuższego wspólnego prefiksu pomiędzy słowem \(sufiks_k\) i zbiorem słów \(\lbrace sufiks_1,\, sufiks_2, \ldots,\, sufiks_{k-1}\rbrace\). W dalszych rozdziałach pokażemy sposób konstrukcji drzewa sufiksowego na podstawie tablicy sufiksowej oraz tablicy LCP.

Oczywiście szukanie głowy w sposób naiwny - poprzez przechodzenie od korzenia w dół drzewa i szukanie pierwszego miejsca, gdzie wstawiany sufiks dokonuje rozgałęzienia - niczym nie różni się od algorytmu kwadratowego. Skorzystamy z dowiązań sufiksowych, aby szybko znajdować głowę \(k\)-tego sufiksu. Oznaczmy przez \(parent(v)\) rodzica wierzchołka \(v\) w drzewie \(T\) (w sensie wierzchołków jawnych). Przyjmujemy \(parent(root) = root\). Korzystamy z następujących własności drzew sufiksowych:

1. \(head_i\) jest potomkiem \(Suf(head_{i-1})\)
2. \(Suf(v)\) jest potomkiem \(Suf(parent(v))\) dla każdego \(v \in T\)

Korzystając z wymienionych właściwości drzewa \(T\) możemy zaoszczędzić sporo pracy, wyszukując głów idąc niejako "na skróty" przez dowiązania sufiksowe. Aby wydusić odpowiednią złożoność, musimy jeszcze przyspieszyć nieco poruszanie się w dół drzewa. Rózróżniamy dwa sposoby schodzenia w dół drzewa:

1. Wolne (\(slowfind\)), czyli przemieszczanie się znak po znaku. Używane, gdy nie wiemy wystarczająco wiele o szukanym słowie, aby przemieszczać się w sposób szybki. Schodzenie wolne stosujemy np. w algorytmie sprawdzania, czy dane słowo \(y\) jest podsłowem tekstu \(x\) - nie mamy pewności, czy \(y\) występuje, więc ostrożnie testujemy kolejne znaki drzewa zbudowanego z tekstu \(x\).
2. Szybkie (\(fastfind\)), gdy wyszukujemy w drzewie słowa, o którym wiemy, że na pewno je znajdziemy, a bardziej interesuje nas gdzie (w jakim węźle jawnym lub niejawnym) je znajdziemy. Pozwala to w czasie stałym omijać całe krawędzie drzewa, niezależnie od tego jak długie podsłowa one reprezentują.

Funkcja dwuargumentowa \(slowfind(v,\, y)\) (analogicznie \(fastfind(v,\, y)\)) zwraca węzeł (być może niejawny), na którym kończy się zejście w dół drzewa zapoczątkowane w węźle \(v\), w poszukiwaniu słowa \(y\). Po drodze znajdujemy jeszcze wartość \(Suf(head_{i-1})\) - jest to ostatni jawny węzeł drzewa na ścieżce z korzenia do \(head_i\) włącznie. Na potrzeby opisu algorytmu oznaczmy jeszcze przez \(leaf_k\) węzeł końcowy (liść drzewa), powstały po dodaniu \(k\)-tego sufiksu. Mając już cały arsenał pojęć i pomocniczych operacji, możemy opracować dokładny algorytm konstrukcji drzewa sufiksowego.

Twierdzenie
Algorytm McCreighta buduje drzewo sufiksowe tekstu o długości \(n\) w czasie \(O(n)\), przy założeniu \(\vert \Sigma \vert = O(1)\).

Dowód
Rozważmy oddzielnie czas działania wszystkich wykonań \(slowfind\) i \(fastfind\). Wszystkie pozostałe operacje działają w czasie stałym. Niech \(depth(v)\) oznacza głębokość węzła \(v\) w drzewie sufiksowym, tzn. liczbę węzłów w skompresowanym drzewie na ścieżce od korzenia do \(v\).

Operacja \(fastfind\) zwiększa głębokość, na której przebywamy. Przejście do rodzica oraz przejście dowiązaniem sufiksowym zmniejsza tę głębokość. Zachodzi \(depth(v) \leq depth(Suf(v)) + 1\). Oznacza to, że w każdej iteracji algorytmu najpierw zmniejszamy głębokość o co najwyżej 2, a następnie zwiększamy tę głębokość. Nie możemy jej zwiększać w nieskończoność, bo liczba węzłów drzewa jest w danej fazie liniowa względem numeru iteracji (rzędu \(2n\)), zatem po wszystkich iteracjach wykonamy co najwyżej liniowo wiele przemieszczeń po węzłach drzewa w trakcie \(fastfind\).

Wykażemy teraz, że czas spędzony na wykonywaniu \(slowfind\) także jest liniowy, co zakończy dowód. Przez zapis \(\vert head_i \vert\) rozumiemy odległość węzła \(head_i\) od korzenia w sensie nieskompresowanego drzewa sufiksowego. Używamy \(slowfind\) aby znaleźć \(head_i\) rozpoczynając od \(Suf(head_{i-1})\). Ponieważ początkowych \(\vert head_{i-1} \vert\) znaków znajdujemy przy pomocy \(fastfind\), praca wykonana przez \(slowfind\) wynosi \(\vert head_i \vert - \vert head_{i-1} \vert + O(1)\). Zatem łącznie wykonamy liniowo wiele operacji:
$$\sum_{i = 2}^{n} \vert head_i \vert - \vert head_{i-1} \vert + O(1) = O(n)$$

Algorytm Ukkonena - konstrukcja online

Algorytm online konstrukcji drzewa sufiksowego będzie stosował odmienną filozofię (a raczej kierunek) działania. Rozważmy najpierw prosty algorytm działający w złożoności kwadratowej. Budujemy nieskompresowane drzewo sufiksowe z kolejnych prefiksów słowa \(x = x_1 x_2 \ldots x_n\): w \(k\)-tej fazie dodajemy w pewnych punktach drzewa \(T_{k-1}\) krawędzie etykietowane znakiem \(x_k\) w taki sposób, aby otrzymać drzewo sufiksowe \(T_k\) dla słowa \(x_1 x_2 \ldots x_k\). Te punkty to miejsca, w których w drzewie \(T_{k-1}\) kończą się sufiksy. Innymi słowy utrzymujemy listę miejsc, gdzie kończą się sufiksy drzewa \(T_{k-1}\) i w kolejnej fazie przedłużamy każdy taki sufiks o symbol \(x_k\), aktualizując tym samym listę. Należy do niej oczywiście dodać nowy sufiks, składający się wyłącznie z symbolu \(x_k\).

Może zdarzyć się tak, że przedłużając pewien sufiks \(sufiks_i\) o symbol \(x_k\) okaże się, że w węźle odpowiadającym "zakończeniu" tego sufiksu istnieje już krawędź etykietowana znakiem \(x_k\). Wtedy oczywiście nie dodajemy w tym punkcie nowej krawędzi, a jedynie aktualizujemy "zakończenie" sufiksu \(sufiks_i\). Całość można opisać następującym pseudokodem:

Postaramy się usprawnić ten algorytm korzystając z pewnej regularności wykonywanych w nim operacji. Łatwo można zaobserwować następujące fakty dotyczące działania algorytmu:

1. Jeśli w pewnej iteracji algorytmu któraś z "końcówek" sufiksu stanie się liściem wskutek dodania nowej krawędzi do drzewa, to taka końcówka zostaje liściem już na zawsze, niezależnie od liczby i kompozycji dodawanych znaków.
2. Jeśli w wewnętrznej pętli dla pewnej wartości \(j\) nie będziemy musieli dodawać nowej krawędzi, ponieważ dla końcówki \(j\)-tego sufiksu potrzebna krawędź już istnieje, to z własności drzew sufiksowych wynika, że istnieje taka krawędź już dla wszystkich dalszych końcówek sufiksów znajdujących się na liście, zatem algorytm dokona jedynie przesunięcia tych końcówek o pojedynczą krawędź w dół drzewa.
3. Zgodnie z definicją dowiązań sufiksowych, zachodzi następująca odpowiedniość między elementami na liście \(L\): \(L[j + 1] = Suf(L[j])\).

Możemy teraz zastanowić się nad wyprowadzeniem analogicznego algorytmu dla drzew skompresowanych wykorzystując powyższe własności.

Własność 1.
Za każdym razem gdy przedłużamy sufiks dodając nowy liść do drzewa sufiksowego, możemy o tym sufiksie już zapomnieć: przy założeniu opisu krawędzi skompresowanych za pomocą dwóch liczb (początek i koniec jakiegoś podsłowa w \(x\)) możemy jako drugiej liczby użyć umownego znacznika nieskończoności \(\infty\). Dzięki temu zachowamy własność online algorytmu, ponieważ taka krawędź reprezentować będzie dowolny tekst zaczynający się w określonym punkcie. Będziemy zatem chcieli przeglądać jedynie te końcówki sufiksów, które wymagać będą przedłużenia nową krawędzią, wykonywać operację dodania takiej krawędzi w czasie stałym i zapominać o takich sufiksach.

Własność 2.
Jeśli rozważając kolejne sufiksy natrafimy na taki, którego nie musimy przedłużać, bo odpowiednia krawędź znajduje się już w drzewie, to nie musimy też przeglądać dalszych, ponieważ dla nich także odpowiednia krawędź występuje. W poprzednim algorytmie aktualizowaliśmy pozycje tych końcówek, tutaj chcemy tego uniknąć.

Własność 3.
Uniknąć tego możemy, o ile potrafimy szybko znajdować kolejne końcówki sufiksów korzystając z dowiązań sufiksowych, aby w razie potrzeby namierzyć kolejne miejsce wymagające rzeczywistej aktualizacji, tzn. dodania krawędzi-liścia. Można zastosować w tym celu ten sam trik, co w algorytmie McCreighta: zapamiętujemy jedynie dowiązania sufiksowe wierzchołków jawnych, a jeśli chcemy znaleźć dowiązanie wierzchołka niejawnego, to najpierw przechodzimy po dowiązaniu sufiksowym jego (jawnego) rodzica w drzewie, a następnie wykonujemy operację \(fastfind\).

Twierdzenie
Algorytm Ukkonena buduje drzewo sufiksowe tekstu o długości \(n\) w czasie \(O(n)\), przy założeniu \(\vert \Sigma \vert = O(1)\).

Dowód
Obrotów wewnętrznej pętli while mamy liniowo wiele - każdy obieg odpowiada dodaniu jednego liścia, a tych jest \(O(n)\). Wszystkie operacje w pętli poza \(fastfind\) wykonujemy w czasie stałym. Należy zatem rozważyć łączną pracę wykonaną przez wszystkie wywołania \(fastfind\) - dowód identyczny do dowodu z algorytmu McCreighta.

Ciekawy przykład

Niech \(Fib'_n\) oznacza \(n\)-te słowo Fibonacciego (dla \(n \geq 3\)) pozbawione dwóch ostatnich liter. Kilka pierwszych słów tej postaci:

• \(Fib'_3 = a\)
• \(Fib'_4 = aba\)
• \(Fib'_5 = abaaba\)
• \(Fib'_6 = abaababaaba\)

Interesujący fakt, którego nie będziemy tutaj udowadniać: takie słowo jest palindromem. Ponadto drzewo sufiksowe dla słów \(Fib'\) wykazuje interesującą regularność, co wynika ze struktury tych słów - każde z nich można przedstawić jako konkatenację odwróconych kolejnych słów Fibonacciego. Tzn. jeśli \(R_k = Fib_k^R\), to wtedy \(Fib'_n = R_1 R_2 \ldots R_{n-2}\).

W poprzednim rozdziale zajmowaliśmy się konstrukcją drzew sufiksowych w postaci skompresowanej. Wróćmy do rozważań nad ich wersją bazową, nieskompresowaną.

Dany jest tekst \(x\) oraz zbudowane na jego bazie nieskompresowane drzewo sufiksowe. Niech dla każdego wierzchołka \(v\) w drzewie \(Label(v)\) oznacza słowo z nim stowarzyszone, a \(EndPos(v)\) oznacza zbiór pozycji w tekście \(x\), na których słowo \(Label(v)\) się kończy. Wtedy sklejając ze sobą wierzchołki drzewa identyczne pod względem zbiorów \(EndPos\) otrzymamy skierowany graf acykliczny, tzw. graf podsłów. Oszczędzamy w ten sposób pamięć nie tylko na wspólnych prefiksach słów, ale także na sufiksach. Zaskakujący okazuje się ogrom tej oszczędności, o czym więcej poniżej.

O ile w drzewie sufiksowym do każdego wierzchołka prowadziła unikalna ścieżka z korzenia, w grafie podsłów takich ścieżek może być więcej. Zanim przejdziemy do dalszych rozważań, zdefiniujmy na nowo etykietę \(Label(v)\) i dowiązanie sufiksowe \(Suf(v)\) dla wierzchołka grafu \(v\). Każdy wierzchołek reprezentuje te podsłowa tekstu, które można zbudować przechodząc wszystkimi możliwymi ścieżkami od korzenia. Uznajmy zatem, że \(Label(v)\) związane będzie z najdłuższym słowem spośród tego zbioru, a \(Suf(v)\) wskazuje na taki wierzchołek \(w\), że \(Label(w)\) jest najdłuższym sufiksem \(Label(v)\) nie należącym do zbioru słów reprezentowanego przez wierzchołek \(v\). Umownie przyjmijmy też, że dowiązaniem sufiksowym korzenia \(root\) grafu podsłów jest jakiś umowny wskaźnik NULL.

Fakt
Zbiór słów reprezentowanych przez wierzchołek grafu podsłów zawiera słowa o długościach będących kolejnymi liczbami całkowitymi od \(c_1\) do \(c_2\) dla pewnych wartości \(c_1\) i \(c_2\). Fakt ten wynika ze sposobu konstrukcji grafu podsłów na podstawie nieskompresowanego drzewa sufiksowego: począwszy od najdłuższego słowa w pewnym zbiorze \(EndPos\), kolejne, krótsze słowa znajdują się na ścieżce dowiązań sufiksowych w drzewie. Na przykład wierzchołek grafu z powyższego przykładu o zbiorze \(EndPos = \lbrace 4 \rbrace\) reprezentuje słowa:

• bb
• abb
• aabb

Czyli dla tego wierzchołka \(c_1 = 2\) i \(c_2 = 4\). Jego dowiązanie sufiksowe wskazuje na wierzchołek o zbiorze \(EndPos = \lbrace 3,\, 4,\, 6 \rbrace\), dla którego zachodzi \(c_1 = c_2 = 1\).

Fakt (o zbiorach \(EndPos\))
Dla dwóch wierzchołków grafu \(v\) i \(w\) takich, że \(Suf(v) = w\) zachodzi \(EndPos(v) \subset EndPos(w)\) (podzbiór właściwy - to ważne).

Z powyższego faktu wynikają dalsze konsekwencje. Zauważmy bowiem, że jeśli weźmiemy dwa dowolne różne wierzchołki grafu podsłów, to albo przecięcie ich zbiorów \(EndPos\) będzie puste, albo zbiór \(EndPos\) jednego z nich będzie podzbiorem właściwym zbioru \(EndPos\) drugiego z nich. Tym samym widać, że dowiązania sufiksowe wierzchołków grafu podsłów tworzą drzewo. Prowadzi to prosto do twierdzenia o rozmiarze grafu podsłów.

Twierdzenie
Graf podsłów \(G\) zbudowany z tekstu o długości \(n\) ma \(O(n)\) wierzchołków.

Dowód
Jak pokazaliśmy, dowiązania sufiksowe wierzchołków tworzą drzewo. Co więcej, takie drzewo ma co najwyżej \(n\) liści - liść będzie wierzchołkiem grafu, dla którego \(EndPos\) jest zbiorem jednoelementowym. Gdybyśmy mogli uznać, że każdy wewnętrzny węzeł takiego drzewa ma przynajmniej dwóch potomków, to byłby to koniec dowodu. Jednak tak się nie dzieje np. dla tekstu postaci \(a^n\), gdzie mamy jeden liść oraz \(n - 1\) węzłów wewnętrznych.

Z faktu o zbiorach \(EndPos\) wynika, że w relacji rodzic-dziecko w drzewie dowiązań sufiksowych zbiór \(EndPos\) rodzica zawiera zawsze jakiś indeks, który nie znajduje się w zbiorze \(EndPos\) potomka. Zatem ze względu na drzewiastą strukturę zawierania się zbiorów \(EndPos\) oraz liniową liczbę wszystkich indeksów, liczba takich jednopotomkowych węzłów wewnętrznych jest także co najwyżej liniowa. Koniec dowodu.

Twierdzenie
Graf podsłów \(G\) zbudowany z tekstu o długości \(n\) ma \(O(n)\) krawędzi.

Dowód
Rozważmy dowolne skierowane drzewo rozpinające graf \(G\). Skierowanie oznacza tutaj, że zaczynając w korzeniu grafu możemy osiągnąć wszystkie inne wierzchołki grafu idąc tylko zgodnie ze skierowaniem krawędzi. Takie drzewo ma oczywiście \(O(n)\) krawędzi.

Zastanówmy się, ile pozostaje w \(G\) krawędzi, które nie należą do drzewa rozpinającego. Rozpatrzmy jedną taką krawędź, postaci \(v_1 \stackrel{\alpha}{\to} v_2\). Zbudujmy słowo \(w\) postaci \(p \alpha s\), gdzie \(p\) jest prefiksem \(w\) zbudowanym poprzez przejście wybranym drzewem rozpinającym z korzenia do wierzchołka \(v_1\), \(\alpha\) jest symbolem etykietującym wybraną krawędź niedrzewową, \(s\) jest sufiksem słowa \(w\) i zarazem całego tekstu, zbudowanym poprzez przejście dowolną ścieżką z \(v_2\) do końca grafu \(G\). W ten sposób z przejściem krawędzią niedrzewową utożsamiamy pewien sufiks całego tekstu. Sufiksów jest liniowo wiele, a zatem liczba krawędzi niedrzewowych także jest liniowa, co kończy dowód.

Twierdzenie
Graf podsłów zbudowany z tekstu o długości \(n \geq 3\) ma co najwyżej \(2n - 1\) wierzchołków i co najwyżej \(3n - 4\) krawędzi.

Dowód
Ćwiczenie dla Czytelnika - udowodnić, że nie da się uzyskać więcej i podać przykłady tekstów, które osiągają to ograniczenie dla dowolnego \(n \geq 3\).

Algorytm konstrukcji grafu podsłów

Przedstawiamy działający w liniowym czasie algorytm konstrukcji grafu podsłów. Algorytm ten jest typu on-line, konstruuje graf w kolejnych fazach, dodając po jednym symbolu do tekstu, na podstawie którego graf jest zbudowany. W fazie \(k\)-tej algorytm konstruuje graf podsłów \(G_k\) dla \(k\)-znakowego prefiksu całego tekstu na podstawie grafu podsłów \(G_{k-1}\). Oznaczmy przez \(pref_i(x)\) prefiks tekstu \(x\) o długości \(i\), tzn. słowo \(x_1 x_2 \ldots x_i\).

Zastanówmy się jakie zmiany należy wprowadzić do grafu \(G_{k-1}\), aby uzyskać graf \(G_k\). Na pewno musimy stworzyć nowy wierzchołek, reprezentujący podsłowa tekstu \(pref_k(x)\), które nie są podsłowami tekstu \(pref_{k-1}(x)\). Oprócz tego być może będziemy musieli rozbić pewien wierzchołek po dodaniu nowego znaku, aby zachować zgodność z definicją zbiorów \(EndPos\).

Obserwacja: pewne podsłowo \(y\) słowa \(x\) jest reprezentantem wierzchołka grafu podsłów (tzn. dla pewnego \(v\) zachodzi \(Label(v) = y\)) wtedy i tylko wtedy, gdy albo \(y\) jest prefiksem \(x\), albo wśród zbioru wystąpień \(y\) w \(x\) znajdują się dwa takie, które poprzedzone są różnymi znakami z alfabetu. Wynika to z definicji zbioru \(EndPos\).

Weźmy najdłuższy sufiks słowa \(pref_k(x)\), który występuje w tym słowie więcej, niż jeden raz - oznaczmy to słowo \(tail\). Jeśli \(tail\) jest słowem pustym, to niczego już nie robimy. W przeciwnym wypadku znajdźmy w grafie \(G_{k-1}\) wierzchołek \(v\) odpowiadający słowu \(tail\) (tzn. istnieje ścieżka z \(root\) do \(v\), która "buduje" słowo \(tail\), ale niekoniecznie \(Label(v) = tail\)). Jeśli słowo \(tail\) występowało w \(pref_{k-1}(x)\) zawsze poprzedzone tym samym znakiem \(\alpha\), natomiast ostatnie wystąpienie \(tail\) w \(pref_k(x)\) poprzedzone jest znakiem \(\beta\) różnym od \(\alpha\), to wtedy w grafie \(G_k\) wierzchołek \(v\) rozbijamy na dwa nowe wierzchołki \(v'\) i \(v''\):

• \(v'\) będzie reprezentował słowa ze zbioru definiowanego przez \(v\) o długościach mniejszych lub równych długości słowa \(tail\) - zachodzi oczywiście \(Label(v') = tail\)
• \(v''\) będzie reprezentował pozostałe słowa odpowiadające wierzchołkowi \(v\), tzn. dłuższe od \(tail\)

Skąd wiadomo, że istnieje tylko jeden wierzchołek, który należy rozbić i dlaczego rozbicie przebiega wedle tych reguł? Po pierwsze, jeśli któreś słowo było prefiksem lub występowało poprzedzone dwoma różnymi znakami w \(pref_{k-1}(x)\), to nie straci ono żadnej z tych własności w \(pref_k(x)\). Po drugie, spośród potencjalnie dużego zbioru słów, które w \(pref_k(x)\) pojawiają się z dwoma różnymi znakami po lewej stronie, ale jeszcze w \(pref_{k-1}(x)\) występują tylko z jednym, weźmy najdłuższe takie słowo \(y\) oraz przyjmijmy, że jest związane z pewnym wierzchołkiem \(v\).

Teraz zapiszmy \(Label(v)\) jako \(p \alpha y\). Możemy tak zrobić, bo \(y\) na pewno nie jest \(Label\) dla żadnego wierzchołka grafu (\(p\) może być słowem pustym, ale na pewno występuje jakieś \(\alpha\)). Zatem w słowie \(pref_{k-1}(x)\) każde wystąpienie podsłowa \(y\) było poprzedzone \(p \alpha\), ale w słowie \(pref_{k}(x)\) już tak się nie dzieje: \(\beta y\) musi być sufiksem \(pref_{k}(x)\) dla \(\alpha \neq \beta\). Ponieważ \(\beta y\) nie wystąpiło wcześniej w \(pref_{k-1}(x)\), to \(y\) jest dokładnie słowem \(tail\) - najdłuższym sufiksem występującym więcej niż jeden raz w całym słowie \(pref_k(x)\). Co więcej, \(y\) i wszystkie jego sufiksy należące do zbioru słów reprezentowanych przez wierzchołek \(v\) występują jako sufiksy \(pref_k(x)\), natomiast słowa z tego samego zbioru dłuższe od \(y\) już nie. Z tego wynika słuszność rozbicia \(v\) na \(v'\) i \(v''\). Rozważyliśmy w tym momencie wszystkie podsłowa \(pref_k(x)\), zatem potrzeby rozbijania innych wierzchołków nie ma.

Dygresja: powyższe rozważania są także inną metodą udowodnienia liniowej liczby wierzchołków grafu podsłów - pokazaliśmy, że wraz z każdym kolejnym znakiem tekstu dodajemy do grafu jeden albo dwa wierzchołki.

Aby efektywnie aktualizować graf \(G_{k-1}\) do \(G_k\), potrzebujemy oprócz dowiązań sufiksowych jeszcze dodatkowej informacji zapamiętywanej dla krawędzi. Krawędzie dzielimy na:

• twarde - krawędzie tworzące najdłuższe ścieżki z korzenia do wszystkich wierzchołków grafu; innymi słowy przejście wyłącznie krawędziami twardymi z korzenia \(root\) do dowolnego wierzchołka \(v\) generuje słowo \(Label(v)\),
• miękkie - wszystkie pozostałe.

Oznaczmy przez \(v_{tail_k}\) wierzchołek grafu \(G_k\), który zawiera ogon (sufiks \(tail\) zgodnie z wcześniejszą definicją) słowa \(pref_k(x)\). Wyróżnijmy też ujście grafu \(G_k\) - wierzchołek \(sink_k\) taki, że \(EndPos(sink_k) = \lbrace k \rbrace\). Łatwo zauważyć, że w każdej fazie tworzymy nowe ujście, które podłączamy do ujścia poprzedniego oraz inicjalnie (dla słowa pustego) ujście jest korzeniem: \(sink_0 = root\). Ujście jest jednym z co najwyżej dwóch wierzchołków, które tworzymy w jednej iteracji algorytmu.

Użycie dowiązań sufiksowych oraz rozróżnianie pomiędzy krawędziami twardymi i miękkimi pozwala szybko znajdować wierzchołek, który potencjalnie należy rozbić. Zauważmy bowiem, że \(Suf(sink_{k-1}) = v_{tail_{k-1}}\), a zatem jeśli \(x_k = \alpha\) i znajdziemy najmniejsze takie \(j\), że \(Suf^j(sink_{k-1}) = v\), gdzie \(v\) zawiera krawędź \(v \stackrel{\alpha}{\to} w\), to wtedy \(w = v_{tail_k}\). Jeśli takie \(j\) nie istnieje, tzn. przechodząc dowiązaniami sufiksowymi począwszy od \(sink_{k-1}\) dojdziemy aż do korzenia \(root\) i nie znajdziemy wierzchołka o wychodzącej krawędzi etykietowanej \(\alpha\), to znaczy, że \(tail_k\) jest słowem pustym i tym samym symbol \(\alpha\) wystąpił po raz pierwszy w \(pref_k(x)\).

Jeśli jednak takie \(v\) istnieje, to \(w\) należy rozbić na \(w'\) i \(w''\) wtedy i tylko wtedy, gdy krawędź \(v \stackrel{\alpha}{\to} w\) jest miękka. Zapiszmy bowiem \(tail_k\) jako \(y \alpha\). Podsłowo \(y\) występuje przynajmniej dwukrotnie w \(pref_{k-1}\) i jest poprzedzone zawsze tym samym znakiem \(\beta\). W przeciwnym wypadku krawędź \(v \stackrel{\alpha}{\to} w\) byłaby twarda i zachodziłoby \(Label(w) = y \alpha\). Co więcej \(\alpha \neq \beta\), bo w przeciwnym wypadku \(y\alpha\) nie byłoby najdłuższym sufiksem występującym przynajmniej dwukrotnie w \(pref_k(x)\), czyli nie byłoby słowem \(tail_k\). To znaczy, że właśnie powstało nowe wystąpienie \(y \alpha\), przed którym znajduje się inny znak, niż przed każdym wcześniejszym wystąpieniem tego słowa i należy dokonać rozbicia węzła \(w\).

Rozważyliśmy już wszystkie koniecznie aktualizacje grafu po dodaniu nowego znaku oraz opisaliśmy pomocne rozróżnienie krawędzi. Możemy teraz przystąpić do określenia pełnego algorytmu.

Twierdzenie
Powyższy algorytm konstruuje graf podsłów słowa \(x\) o długości \(n\) w czasie \(O(n)\).

Uwaga: podobnie jak w rozdziale poprzednim zakładamy, że mamy do czynienia z alfabetem stałego rozmiaru. W przeciwnym wypadku należy przemnożyć złożoność czasową przez czynnik \(O(\log \vert \Sigma \vert)\).

Dowód
Każdą operację w algorytmie poza rozbiciem wierzchołka wykonujemy w czasie stałym. Stworzenie nowego wierzchołka \(v'\) zajmuje czas proporcjonalny do liczby krawędzi wychodzących z klonowanego wierzchołka \(v\) - czas ten jest sumarycznie ograniczony przez liczbę wszystkich krawędzi grafu, których jest liniowo wiele. Jedynym potencjalnie problematycznym punktem jest ostatnia pętla while, która nie dodaje nowych krawędzi (jedynie przekierowuje istniejące) i na pierwszy rzut oka wydaje się, że tam właśnie złożoność może się zepsuć. Dla uproszczenia dowodu będziemy obliczać liczbę iteracji obu pętli while pomimo wiedzy, że liczba iteracji pierwszej z nich musi być ograniczona ze względu na udowodniony wcześniej liniowy rozmiar grafu.

Oznaczmy przez \(Depth(v)\) głębokość dowiązań sufiksowych wierzchołka \(v\), tzn. taką najmniejszą liczbę \(j\), że \(Suf^{j} (v) = root\). Wtedy niech \(SufPath(v)\) będzie zbiorem wierzchołków \(\lbrace Suf^1(v),\, Suf^2(v), \ldots,\, Suf^{Depth(v)}(v) \rbrace\). Rozważmy parę wierzchołków \(v\) i \(w\) takich, że krawędź \(v \stackrel{\alpha}{\to} w\) jest twarda. Z tego wynika, że dla każdego \(w' \in SufPath(w)\) istnieje krawędź \(v' \stackrel{\alpha}{\to} w'\), gdzie \(v' \in SufPath(v)\) i nie istnieją inne krawędzie o etykiecie \(\alpha\) wchodzące do wierzchołków ze zbioru \(SufPath(w)\). Zatem jeśli sumarycznie z wierzchołków należących do \(SufPath(v)\) wychodzi \(k_1\) twardych oraz \(k_2\) miękkich krawędzi \(\alpha\), to zachodzi
$$\vert SufPath(w) \vert = k_1 + 1 = \vert SufPath(v) \vert - k_2 + 1.$$

Wróćmy do kodu obu pętli while. W \(i\)-tej fazie algorytmu zaczynamy od stworzenia krawędzi twardej \(sink_{i-1} \stackrel{\alpha}{\to} sink_i\). Zarówno w jednej jak i drugiej pętli tworzymy nowe albo przyłączamy już istniejące miękkie krawędzie z wierzchołków ze zbioru \(SufPath(sink_{i-1})\) do wierzchołków ze zbioru \(SufPath(sink_i)\). Z powyższej równości wynika, że z każdą taką miękką krawędzią metaforycznie "skracamy" zbiór \(SufPath(sink_i)\). Nie należy jeszcze zapominać o sytuacji, gdy rozbijamy pewien wierzchołek na ścieżce sufiksowej. Wtedy wkładamy nowy wierzchołek gdzieś w środku \(SufPath(sink_i)\). Finalnie otrzymujemy nierówność:
$$\vert SufPath(sink_{i}) \vert \leq \vert SufPath(sink_{i-1}) \vert - k + 2,$$
gdzie \(k\) oznacza sumaryczną liczbę obrotów obu pętli while w \(i\)-tej fazie algorytmu. Oczywisty wniosek: łączna liczba obrotów pętli jest liniowa ze względu na długość tekstu, co kończy dowód.

Zastosowania

Graf podsłów ma wszystkie atuty drzewa sufiksowego oraz kilka dodatkowych:

• Pomimo niebanalnej teorii stojącej za nim, algorytm liniowej konstrukcji grafu podsłów jest prostszy, niż analogiczny algorytm dla drzewa sufiksowego.
• Wygoda implementacyjna i użytkowa wynikająca z nieskompresowanej postaci grafu.
• Grafy podsłów także można kompresować. Dla niektórych tekstów otrzymujemy w ten sposób reprezentację rozmiaru subliniowego.
• Konstrukcja grafu może także pomóc w dostrzeżeniu pewnych regularności w tekstach. Ciekawym przykładem są grafy podsłów dla słów Fibonacciego.

Relacje między drzewami i tablicami sufiksowymi

Pokażemy najpierw jak skonstruować tablicę sufiksową mając drzewo sufiksowe.

W celu znalezenia początkowych pozycji sufiksów w porządku leksykograficznym przechodzimy drzewo sufiksowe metodą DFS, zakładając, że dla każdego węzła lista jego synów podana jest w kolejności leksykograficznej etykiet krawędzi prowadzących do synów. Wystarczy sprawdzać piewsze symbole tych etykiet. Załóżmy, że w liściach mamy początki sufiksów, które do nich prowadzą. Kolejność odwiedzania liści w naszym przejściu metodą DFS automatycznie generuje elementy tablicy sufiksowej.

Pokażemy teraz jak skonstruować drzewo sufiksowe mając tablicę sufiksową. Dowiedziemy konstruktywanie następujący istotny fakt: jeśli znamy tablicę sufiksową \(SA\) i tablicę \(LCP\), to drzewo sufiksowe dla danego tekstu możemy skonstruować w czasie liniowym.

Przypuśćmy, że \(SA = [i_1,\, i_2,\ldots,\, i_n]\), a więc:
$$sufiks_{i_1} < sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.$$

Opiszemy w jaki sposób wstawiamy kolejny sufiks \(sufiks_{i_k}\) do drzewa. Załóżmy, że w każdym węźle drzewa trzymamy długość tesktu, który ten węzeł reprezentuje (jako pełna etykieta od korzenia do węzła). Niech \(sufiks_{i_{k-1}}\) będzie poprzednio wstawionym sufiksem, a \(u\) poprzednio utworzonym liściem. Wtedy wstawienie \(sufiks_{i_k}\) polega na znalezieniu maksymalnego wspólnego prefiksu \(p\) tekstów \(sufiks_{i_{k-1}}\) i \(sufiks_{i_k}\). Niech \(sufiks_{i_k} = p \cdot s\). Znajdujemy węzeł \(v\) odpowiadający ścieżce od korzenia etykietowanej \(p\). Podstawowym trikiem jest to, że węzła \(v\) szukamy nie od korzenia, ale od ostatnio utworzonego liścia \(u\). Jeśli takiego węzła \(v\) nie ma (jest wewnątrz krawędzi) to go tworzymy. Następnie dodajemy nowy liść \(w\), odpowiadający sufiksowi \(sufiks_{i_k}\) oraz krawędź \((v,\, w)\) etykietowaną \(s\).

Z tablicy \(LCP\) odczytujemy długość słowa \(p\). W celu znalezienia \(v\) posuwamy się ścieżką od \(u\) w górę drzewa, aż znajdziemy węzeł oddalony od korzenia o \(\vert p \vert\). Przechodząc drzewo przemieszczamy się po węzłach drzewa, przeskakując potencjalnie długie teksty na krawędziach. Koszt operacji wstawienia wynosi \(Depth(u) - Depth(v) + O(1)\) - najpierw wykonujemy tyle cofnięć, ile trzeba aby przejść z \(u\) do \(v\), a potem dodajemy nowy liść. Po każdym dodanym liściu zwiększamy głębokość o 1, zatem sumaryczna liczba cofnięć jest liniowa i cały algorytm działa w czasie \(O(n)\).

Słowo \(p\) jest najdłuższym wspólnym prefiksem słów \(sufiks_{i_{k-1}}\) i \(sufiks_{i_k}\). Kluczowe znaczenie w operacji ma znajomość wartości \(\vert p \vert = LCP[k-1]\) - wiemy kiedy się zatrzymać idąc do góry od węzła \(u\) w kierunku korzenia.

Szkielet grafu podsłów

Graf podsłów tak naprawdę powinien nazywać się grafem sufiksów, w sposób istotny rozróżnia on sufiksy i niesufiksy danego tekstu. Każda ścieżka od źródła do ujścia w tym grafie reprezentuje pewien sufiks (ale niekoniecznie każdy sufiks jest taką ścieżką, może się kończyć wewnątrz grafu). Jeśli mamy dwa słowa \(w\) i \(v\), z których jedno jest sufiksem a drugie nie jest, to nie prowadzą one do tego samego węzła. Pokażemy pewne związki między trzema strukturami danych reprezentującymi sufiksy słowa.

Zanim przejdziemy do relacji między grafami podsłów i drzewami sufiksowymi pokażemy, że graf podsłów jest w istocie zadany przez drzewo składające się z krawędzi na najdłuższych ścieżkach (krawędzie twarde z poprzedniego rozdziału). Drzewo to nazywamy szkieletem grafu podsłów słowa \(w\) i oznaczmy przez \(S=Szkielet(w)\). Każdy węzeł \(S\) utożsamiamy ze słowem reprezentującym ścieżkę od korzenia do tego węzła. Jeśli mamy drzewo \(S\), to tablica dowiązań sufiksowych jest liczona tak samo jak tablica prefikso-sufiksów dla pojedynczego tekstu:

• \(Suf(u)\) jest najdłuższym właściwym (być może słowem pustym - korzeniem \(S\)) sufiksem \(u\), który należy do \(S\).
• Liczenie dowiązań sufiksowych odpowiada liczeniu tablicy \(P\) dla drzewa wielu wzorców, patrz rozdział 12.

Zostaje jedynie uzupełnienie grafu podsłów pozostałymi krawędziami (krawędziami miękkimi).

Relacje między drzewami sufiksowym i grafami podsłów

W drzewie sufiksowym załóżmy, że wszystkie sufiksy tekstu odpowiadają wierzchołkom, choćby miały one mieć tylko jednego syna. Można sztucznie dodac na końcu tekstu jakiś znacznik (ang. endmarker), który powoduje utworzenie takich wierzchołków, a następnie znacznik ten usunąc.

Zatem niech \(T\) będzie drzewem sufiksowym słowa \(w\), natomiast \(S = Szkielet(w^R)\) będzie szkieletem grafu podsłów odwróconego słowa \(w^R\). Oznaczmy przez \(Nodes(T)\) zbiór podsłów odpowiadających węzłom drzewa \(T\) i \(Nodes(S)\) zbiór podsłów odpowiadających węzłom grafu \(S\).

Lemat
Niech dane będą \(S = Szkielet(w^R)\) i \(T\) - drzewo sufiksowe słowa \(w\) z dodanymi węzłami dla wszystkich sufiksów \(w\) (dodajemy endmarker w czasie konstrukcji drzewa, a na końcu usuwamy). Wtedy zachodzi:

1. Reprezentanci węzłów drzewa \(S\) są odwotnościami reprezentantów węzłów drzewa \(T\), inaczej mówiąc \(Nodes(S) = \lbrace u^R : u \in Nodes(T) \rbrace \).
2. Drzewo \(S\) jest drzewem dowiązań sufiksowych drzewa \(T\).

Dowód

1. \(Nodes(T)\) to słowa, które są sufiksami \(w\) lub takie, które mają dwa różne rozszerzenia w prawo w słowie \(w\). Z drugiej strony \(Nodes(S)\) to słowa, które są prefiksami \(w\) lub takie, które mają dwa różne rozszerzenia w lewo w słowie \(w^R\). Zauważmy, że w odwróconym tekście sufiks staje się prefiksem, a rozszerzenie w prawo staje się rozszerzeniem w lewo. Dowodzi to punktu (1).
2. Drzewo dowiązań sufiksowych daje porządek, w jakim usuwamy symbole od początku słowa do końca. Zatem jeśli tekst odpowiadający węzłowi \(v\in T\) jest równy \(w = s_1 s_2 \ldots s_k\), to usuwamy w kolejności \(s_1\), \(s_2\) itd. Natomiast jeśli odwrócimy kolejność (będziemy wtedy wstawiać to, co usuwaliśmy w odwrotnej kolejności), to otrzymamy słowo \(s_k s_{k-1} \ldots s_1\), które odpowiada słowu \(w^R\). Inaczej mówiąc odwrotności krawędzi drzewa sufiksowego czytane od korzenia do danego węzła \(v\) dają ścieżkę od korzenia do węzła odpowiadającego \(v\) w grafie podsłów. Wynika stąd bezpośrednio teza punktu (2), co kończy uzasadnienie prawdziwości lematu.

Rozważamy problem Najkrótszego Wspólnego Nadsłowa (NWN). Na wejściu mamy zbiór słów \(S\) o sumarycznym rozmiarze \(n\) i chcemy znaleźć najkrótsze słowo (nadsłowo albo z angielskiego superstring), zawierające każde słowo ze zbioru \(S\) jako podsłowo. Problem ten jest \(NP\)-trudny. Rozważymy jeden z prostszych algorytmów aproksymacyjnych dla tego problemu - algorytm \(GREEDY\) (zachłanny). Do końca tego rozdziału zakładamy, że \(S\) jest bezinfiksowy, tzn. żadne słowo z \(S\) nie jest podsłowem innego słowa z \(S\).

Dla słów \(x\) i \(y\) oznaczmy przez \(ov(x,\, y)\) najdłuższy sufiks \(x\), będący prefiksem \(y\), zatem jeśli \(ov(x,\, y) = z\), to \(x = x'z\) i \(y = z y'\). Oznaczmy \(x \oplus y = x'y'\). Słowo \(z\) nazywamy nakładką (ang. overlap) słów \(x\) i \(y\).

Zdefiniujmy graf nakładkowy \(G = (V,\, E)\), gdzie \(V = S\) oraz \(dist(u,\, v) = ov(u,\, v)\). Każde nadsłowo odpowiada pewnej ścieżce Hamiltona w tym grafie, długością tej ścieżki jest suma wielkości kolejnych nakładek. Algorytm \(GREEDY\) działa w ten sposób, że wybiera kolejno krawędzie o maksymalnej długości.

Zdefiniujmy przez \(greedy(S)\) sumaryczną wartość długości nakładek realizowanych przez algorytm \(GREEDY\), podobnie niech \(opt(S)\) oznacza sumaryczną długość nakładek dla optymalnego algorytmu \(OPT\), który znajduje najcięższą ścieżkę Hamiltona w naszym grafie \(G\). Możemy to zapisać następująco:
$$greedy(S) = \vert S \vert - \vert GREEDY(S) \vert,\ opt(S) = \vert S \vert - \vert OPT(S) \vert$$

Obliczenie \(OPT(S)\) jest \(NP\)-zupełne, dlatego też musimy się zadowolić algorytmem aproksymacyjnym. \(GREEDY\) jest najlepszym znanym takim algorytmem w sensie sumy nakładek. Udowodnimy następujący fakt.

Twierdzenie (o jakości algorytmu \(GREEDY\))

• Algorytm \(GREEDY\) \(\frac{1}{2}\)-aproksymuje algorytm optymalny w sensie sumy nakładek, tzn. \(greedy(S) \geq \frac{1}{2} opt(S)\).
• W pesymistycznym przypadku \( \frac{1}{2} \) to najlepszy współczynnik dla algorytmu \(GREEDY\).

Dowód
Niech \(opt'(S)\) będzie długością ścieżki optymalnej w \(G\) przy dodatkowym warunku, że mamy krawędź \(u \rightarrow v\), gdzie \(overlap = ov(u,\, v)\) jest maksymalne. Pokażemy najpierw, że wartość ta niewiele różni się od \(opt(S)\). Zachodzi
$$(*) \quad opt'(S) \geq opt(S) - overlap$$

Niech \(\pi\) będzie ścieżką wygenerowaną przez \(OPT\). Rozważamy przypadki:

1. \(u\) jest przed \(v\) na \(\pi\).

   Wtedy ścieżka ma postać:
   $$\pi = w_1 \stackrel{*}{\longrightarrow} w_2 \rightarrow u \rightarrow w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow v \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6$$
   Możemy ją zamienić na ścieżkę dla \(opt'\) tracąc jedynie w sumie \(overlap\), ponieważ "tracimy" dwie nakładki, a zyskujemy \(ov(u,\, v)\), maksymalną nakładkę.
   $$\pi' = w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow w_1\stackrel{*}{\longrightarrow} w_2 \rightarrow u \rightarrow v \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6$$
   Tracimy wagi (nakładki) krawędzi \(u \rightarrow w_3\) i \(w_4 \rightarrow v\) natomiast zyskujemy (maksymalną) wagę utworzonej krawędzi \(u \rightarrow v\).

2. \(v\) jest przed \(u\) na \(\pi\).

   Wtedy ścieżka ma postać:
   $$\pi = w_1 \stackrel{*}{\longrightarrow} w_2 \rightarrow v \rightarrow w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow u \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6$$
   Podobnie jak poprzednio możemy ją zamienić na następującą ścieżkę dla \(opt'\):
   $$\pi' = w_1 \stackrel{*}{\longrightarrow} w_2 \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6 \rightarrow w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow u \rightarrow v $$
   W ten sposób tracimy jedynie w sumie co najwyżej \(overlap\), ponieważ "tracimy" trzy nakładki, z których dwie to \(ov(w_2,v),\; ov(u,w_5)\), a zyskujemy \(ov(u,\, v)+ov(w_2,w_5)\).

   Zauważmy, że
   $$ov(w_2,v)+ov(u,w_5) \; \le ov(u,\, v)+ov(w_2,w_5).$$
   Wynika to stąd że z maksymalności nakładki \(ov(u,v)\), dla prefiksu \(v'\) słowa v długości \(ov(u,v)\) wynikają równości:
   $$ov(w_2,v)=ov(w_2,v'),\ \ ov(u,w_5)=ov(v',w_5).$$
   Zatem $$ov(w_2,w_5)\;\ge \; ov(w_2,v')+ov(v',w_5)-|v'|$$

   Ostatecznie mamy: $$ ov(w_2,w_5)\;\ge \; ov(w_2,v)+ov(u,w_5)-ov(u,v).$$

Kończy to dowód nierówności \((*)\).

Przejdźmy teraz do głównego dowodu, który przeprowadzimy indukcyjnie. Załóżmy, że nierówność \(greedy(S') \geq \frac{1}{2} opt(S')\) jest spełniona dla \(S'\) mających mniej elementów niż \(S\). Z własności \((*)\) wynika, że dla \(S' = S - \lbrace u,\, v \rbrace \cup \lbrace u \oplus v \rbrace\) zachodzi
$$opt(S') + 2\, overlap \geq opt(S)$$

Jednocześnie \(greedy(S) = greedy(S') + overlap\), oraz z założenia indukcyjnego \(greedy(S') \geq \frac{1}{2} opt(S')\). Zbierając te nierówności mamy:
$$greedy(S) = greedy(S') + overlap \geq \frac{1}{2} (opt(S') + 2\, overlap) \geq \frac{1}{2} opt(S).$$

Kończy to dowód pierwszej części twierdzenia. Część druga wynika z przykładu bezpośrednio poprzedzającego twierdzenie.

Liniowa implementacja algorytmu \(GREEDY\): prefikso-sufiksy na drzewie

Początkowy zbiór słów będziemy dalej oznaczać przez \(S = \lbrace s_1,\, s_2,\ldots,\, s_n \rbrace\), a jego elementy będziemy nazywali słowami bazowymi. Niech \(x\) i \(y\) będą słowami, które w pewnym momencie znajdują się w zbiorze słów rozważanych przez algorytm \(GREEDY\). Powstały one przez operację \(\oplus\) wykonaną na pewnych słowach bazowych. Niech więc \(x = x_1 \oplus x_2 \oplus \ldots \oplus x_k\), \(y = y_1 \oplus y_2 \oplus \ldots \oplus y_l\), gdzie \(x_i,\, y_i \in S\) (w zapisie pomijamy nawiasowanie). Pozwala to traktować takie słowa \(x,\, y\) jak ciągi słów bazowych. Na mocy poniższej obserwacji wiemy, że \(ov(x,\, y) = ov(x_k,\, y_1)\).

Obserwacja
Niech \(S\) będzie zbiorem słów oraz \(Ov(S)=\max \lbrace \vert ov(x,\, y)\vert : x \neq y \in S \rbrace\). Jeśli \(\vert ov(u,\, v) \vert = Ov(S)\), to dla dowolnego \(x \in S \setminus \lbrace u,\, v \rbrace\) zachodzi \(ov(u \oplus v,\, x) = ov(v,\, x)\) oraz \(ov(x,\, u \oplus v) = ov(x,\, u)\).

Dowód
Gdyby \(u \oplus v\) i \(x\) miały zakładkę dłuższą niż \(\vert v \vert\), to łatwo zauważyć, że \(u\) i \(x\) miałyby zakładkę dłuższą niż \(\vert ov(u,\, v)\vert\), co nie jest możliwe. Zatem zakładką słów \(u \oplus v\) i \(x\) musi być sufiks \(v\), a więc zakładka \(v\) i \(x\). Analogicznie \(ov(x,\, u \oplus v) = ov(x,\, u)\). Koniec dowodu.

Algorytm będzie tworzył z elementów zbioru \(S\) (rozłączne) ciągi. Na początku są to ciągu jednoelementowe - po jednym na każde słowo bazowe. \(F\) to zbiór początków tych ciągów, a \(L\) - końców. Funkcja \(word(s)\) zwraca ciąg, w którym słowo bazowe \(s\) się znajduje. Przez \(first\) oznaczmy funkcję zwracającą pierwszy wyraz ciągu, a przez \(last\) ostatni. Zauważmy tu, że \(last \circ word\) jest bijekcją z \(F\) na \(L\).

Algorytm znajduje takie \(f \in F\) i \(\ell \in L\), że \(word(f) \neq word(\ell)\), a przy tym \(ov(\ell,\, f)\) jest maksymalne. Następnie łączy ciągi \(word(\ell)\) i \(word(f)\). Powtarza te czynności dopóki wszystkie słowa bazowe nie są w jednym ciągu.

Powiemy jeszcze, że sufiks słowa \(\ell \in S\) jest zakładką, jeśli \(\ell \in L\) oraz dla pewnego \(f \in F\) (takiego, że \(word(\ell) \neq word(f)\)) jest zakładką \(\ell\) i \(f\). W każdym kroku szukamy więc najdłuższej zakładki. Łatwo można zauważyć, że jeśli jakiś sufiks w danym momencie nie jest zakładką, to nigdy już nią nie będzie. Tym samym możemy przejść wszystkie sufiksy słów z \(S\) w kolejności malejącej długości. Jeśli natrafimy na zakładkę, to ją "realizujemy", czyli łączymy odpowiednie ciągi, a jeśli nie, po prostu przechodzimy do następnego sufiksu.

Struktury danych i preprocessing

Zbudujemy tablicę sufiksową \(SA\) słowa \(s_1 \$ s_2 \$ \ldots \$ s_n \$ \) wraz z wartościami \(rank\) i tablicą \(LCP\) (por. rozdział 8). De facto tablica ta odpowiada posortowanej tablicy wszystkich sufiksów słów bazowych. W szczególności znajdują się w niej całe słowa bazowe (posortowane). Dzięki temu możemy łatwo zbudować drzewo trie dla tych słów. Co więcej dla każdej pozycji \(j\) w słowie \(s_i\) będziemy trzymać wskaźnik do węzła w drzewie odpowiadającego \(j\)-temu prefiksowi słowa \(w_i\) (aby móc uzyskać dostęp do tej pozycji w czasie stałym).

Ponadto przechodząc jednokrotnie (od tyłu) tablicę \(SA\) będziemy na podstawie \(LCP\) mogli dla każdego sufiksu \(suf\) znaleźć długość najdłuższego wspólnego prefiksu z (leksykograficznie) najmniejszym i nie mniejszym niż \(suf\) słowem bazowym. Po prostu na pozycjach odpowiadających słowom bazowym wpisujemy ich długość, a na pozostałych - minimum z \(LCP\) i wyniku dla kolejnego w tablicy \(SA\) sufiksu. Dzięki tej wartości dla każdego sufiksu będziemy w stanie szybko wskazać odpowiadający mu pewien węzeł z trie lub stwierdzić, że takiego nie ma.

Zbiory \(L\) będziemy przechowywać jako funkcję charakterystyczną. Ponadto w każdym węźle drzewa trie stworzymy listę \(fLst\) słów z \(F\), którym odpowiadają liście znajdujące się w poddrzewie danego węzła. Funkcję \(word\) zaimplementujemy jako tablicę, przy czym jej wartości będą poprawne tylko dla argumentów z \(L \cup F\), gdyż tylko z nich będziemy korzystać.

Główny krok

Przedstawimy teraz implementację przetwarzania sufiksu \(\ell\) słowa \(s\). Po pierwsze sprawdzamy czy \(\ell \in L\). Jeśli tak, to szukamy odpowiadającego mu węzła w drzewie trie. Jeżeli jest taki węzeł (czyli jest to prefiks jakiegokolwiek słowa z \(S\)), to patrzymy na listę \(fLst\) w tym węźle. Jeśli jest ona pusta lub jej jedynym elementem jest takie \(f'\), że \(word(f') = word(\ell)\), to \(\ell\) nie jest zakładką. W przeciwnym razie na tej liście (na pierwszej lub drugiej pozycji) znajduje się takie \(f\), że zachodzi \(word(f) \neq word(\ell)\).

Słowa \(word(\ell)\) i \(word(f)\) są już dobrymi kandydatami do złączenia. Łączymy więc odpowiednie ciągi (przy okazji zapamiętujemy \(\vert s \vert = ov(\ell,\, f)\) - ta informacja stanie się potrzebna, gdy będziemy chcieli faktycznie dokonać operacji \(\oplus\)), aktualizujemy funkcję \(word\) dla początku i końca otrzymanego ciągu oraz zbiory \(L\) i \(F\). Musimy usunąć \(f\) ze wszystkich list \(fLst\). Aby uczynić to szybko, pamiętamy dla każdego słowa wskaźniki do odpowiednich miejsc we wszystkich listach \(fLst\). Alternatywnie możemy pamiętać zbiór \(F\) jako funkcję charakterystyczną i usuwać zbędne wartości z \(fLst\) dopiero gdy na takie natrafimy przeglądając te listy.

Usuwanie podsłów

Zakładaliśmy, że żadne słowo w zbiorze \(S\) nie jest podsłowem innego. Należałoby więc na samym początku usunąć takie słowa. Mając tablicę sufiksową i \(LCP\) możemy to uczynić w prosty sposób. Wystarczy bowiem sprawdzić, czy \(LCP\) tego słowa i następnego lub poprzednego (sufiksu) w tablicy jest mniejsze niż długość słowa. Jeśli nie, to należy słowo usunąć. Należy przy tym uważać na słowa, które na wejściu pojawiają się wielokrotnie - chcemy usunąć ich wszystkie wystąpienia poza jednym. Następnie możemy po prostu usunąć odpowiednie sufiksy z tablicy \(SA\) i odpowiednio zaktualizować \(LCP\).

Oszacowanie złożoności

Niech \(N\) będzie sumą długości słów w \(S\). Pokażemy, że poza konstrukcją tablicy sufiksowej cały algorytm działa w czasie \(O(N)\) niezależnie od rodzaju alfabetu. Tworzenie tablicy \(LCP\) i naszych dodatkowych opartych na niej wskaźników działa w takiej złożoności. Drzewo trie dla posortowanego ciągu słów konstruuje się również w \(O(N)\). Dane słowo bazowe jest na co najwyżej tylu listach \(fLst\), ile wynosi jego długość, a uzupełniamy je przechodząc od liścia do korzenia w trie, więc sumarycznie jest to \(O(N)\). Posortowanie sufiksów (a właściwie słów z \(S\)) po długości możemy wykonać w czasie proporcjonalnym do sumarycznej ich liczby i długości najdłuższego, co także jest \(O(N)\). Przetwarzanie danego sufiksu odbywa się w czasie stałym, o ile pominie się aktualizację list \(fLst\). Odpowiedni element takiej listy usuwamy w \(O(1)\), więc ten koszt jest amortyzowany przez tworzenie tych list. Cała główna faza działa więc w \(O(N)\), gdyż tyle jest sufiksów. Wreszcie stworzenie wynikowego nadsłowa, czyli dokonanie operacji \(\oplus\) na kolejnych elementach otrzymanego ciągu ma także łączny koszt \(O(N)\), ponieważ zapamiętywaliśmy wartości \(\vert ov \vert\) między kolejnymi słowami.

Ostatecznie algorytm działa w czasie \(O(N+S)\), gdzie \(S\) jest czasem potrzebnym do zbudowania tablicy sufiksowej. W zależności od typu i rozmiaru alfabetu mamy zatem złożoność \(O(N)\) albo \(O(N\log \vert \Sigma \vert)\).

Przypadek słów długości 2

Jeśli wszystkie słowa są dwuznakowe, to istnieje algorytm liniowy znalezienia najkrótszego nadsłowa. Skojarzmy z każdym symbolem \(\alpha \in \Sigma\) wierzchołek grafu \(G\). Dla każdego dwuznakowego słowa \(\alpha_1 \alpha_2\) dodajemy krawędź \(\alpha_1 \to \alpha_2\). W tak powstałym grafie skierowanym szukamy pokrycia ścieżkowego o najkrótszej sumie długości ścieżek. Wtedy każda taka ścieżka jest pewnym podsłowem całego nadsłowa, pokrywającego wszystkie zadane pary znaków.

W ogólnym przypadku minimalne pokrycie ścieżkowe oblicza się znajdując cykl Eulera w odpowiednio zmodyfikowanym grafie \(G\). Modyfikacja polega na dodaniu krawędzi w taki sposób, aby powstał graf eulerowski \(G'\). W \(G'\) znajdujemy cykl Eulera, a następnie usuwamy z niego dodane wcześniej krawędzie. W ten sposób cykl rozpada się na zbiór ścieżek, które pokrywają graf \(G\).

Uwaga: jeśli w \(G\) znajdują się spójne składowe eulerowskie, to wyłączamy je z konstrukcji cyklu Eulera przebiegającego całą resztę grafu. Robimy tak, ponieważ taka spójna składowa wygeneruje odpowiedni fragment (podsłowo) całego nadsłowa niezależnie od reszty grafu i nie ma sensu włączać jej do pełnego cyklu pokrywającego cały graf.

Rozważmy szczególny problem wyszukiwania skompresowanego wzorca: prawdziwy wzorzec jest długości wykładniczej, ale można go zapisać jako ciąg numerów słów Fibonacciego, których konkatenacja daje wzorzec. Jest to bardzo szczególna i prosta sytuacja. Co więcej wzorca szukamy tylko wewnątrz słów Fibonacciego.

Szukanie konkatenacji słów Fibonacciego w słowach Fibonacciego

Niech \(h\) będzie funkcją określoną na napisach złożonych z cyfr 0 i 1. Funkcja \(h\) przekształca napis \(w\), zastępując (niezależnie i równocześnie) każdą cyfrę 0 przez 1 i każdą cyfrę 1 przez napis "10". Na przykład \(h(\)1001\() =\) 101110, \(h( \emptyset ) = \emptyset\) (tzn. funkcja \(h\) zastosowana do pustego napisu jest pustym napisem). Zauważmy, że \(h\) jest różnowartościowa. Przez \(h^k\) oznaczmy \(k\)-krotne złożenie funkcji \(h\) ze sobą. W szczególności, \(h^0\) to funkcja identycznościowa \(h^0(w) = w\).

Interesują nas napisy postaci \(h^k(\)0\()\) dla \(k = 0,\, 1,\, 2,\, 3,\dots\). Oto kilka pierwszych takich napisów:

1. 0
2. 1
3. 10
4. 101
5. 10110
6. 10110101

Mówimy, że napis \(x\) jest podsłowem napisu \(y\), jeżeli występuje w nim jako spójny (tj. jednokawałkowy) podciąg. Mamy dany ciąg liczb naturalnych \(k_1,\, k_2,\ldots,\, k_n\). Celem zadania jest sprawdzenie, czy napis postaci
$$h^{k_1}(\mathtt{0}) \cdot h^{k_2}(\mathtt{0}) \cdots h^{k_n}(\mathtt{0})$$
jest podsłowem \(h^m(\)0\()\) dla pewnego \(m\).

Rozwiązanie algorytmiczne

Dla wygody wprowadźmy oznaczenie \(h_k := h^k(\)0\()\). Słowa \(h_k\) są to tzw. słowa Fibonacciego. Zazwyczaj definiuje się je rekurencyjnie w następujący sposób:
$$h_0 = \mathtt{0}, \quad h_1 = \mathtt{1}, \quad h_k = h_{k-1} h_{k-2} \quad \text{dla } k \ge 2 \qquad (*)$$
Równoważność definicji \((*)\) i tej podanej w treści zadania łatwo pokazać przez indukcję. Rozwiązanie wzorcowe bazuje na definicji przez podstawienie, którą podano w treści zadania. Postać \((*)\) może być jednak pomocna w zrozumieniu niektórych własności, z których będziemy korzystać.

Powiemy, że ciąg \((k_1,\ldots,\, k_n)\) jest dobry, jeżeli \(h_{k_1} \ldots h_{k_n}\) jest podsłowem \(h_m\) dla pewnego \(m\), oraz że jest zły w przeciwnym przypadku. Zadanie polega więc na sprawdzeniu, czy dany na wejściu ciąg \((k_1,\ldots,\, k_n)\) jest dobry.

Pierwsze podejście do rozwiązania tego zadania może wyglądać następująco: generujemy całe słowo \(h_{k_1} \ldots h_{k_n}\), po czym sprawdzamy za pomocą algorytmu wyszukiwania wzorca (np. KMP), czy występuje ono jako podsłowo w \(h_m\) dla odpowiednio dobranego \(m\). Okazuje się, że jeżeli \(h_m\) jest co najmniej \(8\) razy dłuższe niż wyszukiwane słowo, to rozwiązanie takie działa poprawnie. Jednakże już pobieżna analiza pozwala stwierdzić, że takie rozwiązanie nie ma szans powodzenia na już średniego rozmiaru danych wejściowych, gdyż rozmiar słowa \(h_k\) rośnie wykładniczo względem \(k\). Dlatego rozwiązanie, którego szukamy, musi operować tylko na ciągu \((k_1,\ldots,\, k_n)\), bez generowania słowa, które ten ciąg reprezentuje.

Idea rozwiązania wzorcowego polega na przekształcaniu danego ciągu \(w = (k_1,\ldots,\, k_n)\) przez coś w rodzaju funkcji odwrotnej do \(h\). Okazuje się, że dla dużych wyrazów ciągu \(w\) cofanie funkcji \(h\) polega na zwykłym ich zmniejszaniu, a dla małych (nie większych niż \(3\)) trzeba czasem rozpatrywać pewne przypadki szczególne. Operacje, które wykonuje algorytm, mają tę własność, że ciąg dobry przekształcają w ciąg dobry, a zły - w zły. Proces ten doprowadza w końcu do ciągu jednowyrazowego, który oczywiście jest dobry (wtedy ciąg początkowy też był dobry), lub do ciągu, o którym potrafimy stwierdzić, że na pewno jest zły (wtedy początkowy był zły).

Złożoność

Zanim przystąpimy do dowodu poprawności przedstawionego rozwiązania, zastanówmy się nad czasem jego działania. W szczególności upewnijmy się, że algorytm ten się w ogóle zatrzymuje. Pokażemy, że czas działania algorytmu na ciągu \((k_1,\ldots,\, k_n)\) wynosi \(O(k_1 + \ldots + k_n + n)\). Przyjrzyjmy się pojedynczej iteracji pętli while.

Niech \(n\) oznacza bieżącą długość ciągu \(w\), a \(s\) - bieżącą sumę wyrazów ciągu \(w\) z pominięciem pierwszego, jeżeli jest mniejszy od \(2\). Pokażemy, że po wykonaniu instrukcji z głównej pętli programu wartość \(s + n\) maleje o co najmniej \(\lfloor \frac{n}{2} \rfloor\). Faktycznie, początkowe \(0\) lub \(1\) nie zmienia wartości \(s + n\), gdyż nie jest uwzględnione w jej obliczeniu. Inne zmiany, czyli:

• końcowe \(3\) przechodzi w \(1\),
• końcowe \(1\) znika,
• fragment \(1,\, 0\) przechodzi w \(1\),
• fragment \(3,\, 0\) przechodzi w \(1,\, 1\),
• pozostałe wyrazy zmniejszają się o \(1\),

powodują zmniejszenie wartości \(s + n\) o co najmniej \(1\) dla każdego wyrazu lub każdej pary kolejnych wyrazów ciągu \(w\). Wynika stąd, że \(s + n\) maleje łącznie o co najmniej \(\lfloor\frac{n}{2}\rfloor\). Oczywiście jeżeli \(s + n \leq 1\), algorytm się zatrzymuje. Jako że czas wykonania pojedynczej iteracji pętli while wynosi \(O(n)\), jest on w pełni amortyzowany przez zmianę \(s + n\). Zatem całkowity czas działania algorytmu wynosi \(O(s + n)\).

Kilka prostych własności słów \(h_k\)

Potrzebujemy kilku prostych obserwacji o słowach \(h_k\). W przekształceniu \(h(h_{k-1}) = h_k\) każda cyfra 0 w \(h_k\) powstaje w wyniku podstawienia 1 \(\to\) 10, a każda cyfra 1, po której nie występuje 0 - w wyniku podstawienia 0 \(\to\) 1. Wynika stąd w szczególności, że:

1. \(h_k\) zaczyna się od 1 dla \(k \geq 1\),
2. \(h_k\) kończy się na 0 dla \(k\) parzystych, a na \(1\) dla \(k\) nieparzystych,
3. w \(h_k\) nie występuje podsłowo 00,
4. w \(h_k\) nie występuje podsłowo 111 (jest to wniosek z (c) dla słowa \(h_{k-1}\),
5. w \(h_k\) nie występuje podsłowo 101010 (jest to wniosek z (d) dla słowa \(h_{k-1}\)).

Poprawność odpowiedzi false

Uzasadnimy, że kryterium, które odrzuca ciąg \(w\) jako zły, jest poprawne.

Fakt
Jeżeli \(k \notin \lbrace 1,\, 3 \rbrace\), to \(h_k\)0 nie jest podsłowem żadnego \(h_m\).

Jeżeli \(k\) jest parzyste, \(h_k\) kończy się cyfrą 0. Wtedy \(h_k\)0 ma sufiks 00, który nie może być podsłowem żadnego \(h_m\). Jeżeli \(k\) jest nieparzyste i \(k \geq 5\), to można udowodnić (np. korzystając z postaci \((*)\)), że słowo \(h_k\) ma sufiks \(h_5 = \) 10110101, a więc także 10101, czyli 101010 jest sufiksem słowa \(h_k\)0. Ale zgodnie z punktem (e) powyżej, słowo 101010 nie może wystąpić w żadnym \(h_m\). Dowodzi to poprawności faktu.

Poprawność odpowiedzi true

Teraz uzasadnimy, że każda z operacji wykonywanych głównej pętli programu jest poprawna, tzn. że ciąg \(w\) jest dobry po wykonaniu tej operacji wtedy i tylko wtedy, gdy był dobry przed jej wykonaniem. Zauważmy przy tym, że wszystkie operacje poza ostatnią (zmniejszenie wartości wyrazów ciągu o \(1\)) są od siebie niezależne i mogą być wykonane w dowolnej kolejności. Dla ciągu \(w = (k_1,\ldots,\, k_n)\) wprowadzamy oznaczenie \(h_w = h_{k_1} \ldots h_{k_n}\).

Jeżeli w ciągu \(w\), poza pierwszym wyrazem, występuje jakiekolwiek \(0\), to musi być ono poprzedzone przez \(1\) albo \(3\), gdyż w przeciwnym przypadku ciąg \(w\) zostałby odrzucony przy wcześniejszym sprawdzeniu. Ponieważ \(h_1 h_0 =\) 10 \(= h_2\) i \(h_3 h_0 =\) 1010 \(= h_2 h_2\), instrukcje zamiany \(1,\, 0 \to 2\) i \(3,\, 0 \to 2,\, 2\) przekształcają ciąg \(w\) w równoważny ciąg \(w'\), taki że \(h_w = h_{w'}\). To dowodzi, że operacje te są poprawne, ponadto eliminują one wszystkie zera występujące w \(w\) poza być może pierwszym.

Aby pozbyć się początkowego zera zauważmy, że jeżeli \(h_w\) występuje jako podsłowo w \(h_m\), to początkowe zero musi być drugą cyfrą fragmentu 10 \(= h_2\). Oznacza to, że jeżeli na początku ciągu \(w\) zamienimy \(0\) na \(2\), to dla tak otrzymanego \(w'\) słowo \(h_{w'}\) również występuje jako podsłowo w \(h_m\). To dowodzi poprawności operacji \(0 \to 2\).

Uzasadnimy teraz poprawność instrukcji \(3 \to 2\), usunięcia końcowej jedynki i obniżenia wartości wszystkich wyrazów ciągu o \(1\). Załóżmy, że w ciągu \(w\) nie występuje żadne zero. Oznaczmy przez \(w'\) ciąg, który powstaje z \(w\) po zastosowaniu operacji \(3 \to 2\) i usunięcia końcowej jedynki. Operacje te odcinają ostatnią cyfrę \(1\) z \(h_w\), jeżeli ciąg \(w\) kończy się na \(1\) lub \(3\). Zatem \(h_w = h_{w'}\) lub \(h_w = h_{w'}\)1, przy czym w tym pierwszym przypadku ciąg \(w'\) nie kończy się na \(1\) ani na \(3\). Oznaczmy przez \(w''\) ciąg, który powstaje z \(w'\) przez zmniejszenie wszystkich wyrazów o \(1\).

Najpierw udowodnimy, że jeżeli \(w\) jest dobry, to \(w''\) także jest dobry. Załóżmy, że \(h_w\) jest podsłowem \(h_m\) i zastanówmy się, z czego powstaje to podsłowo w przekształceniu \(h(h_{m-1}) = h_{m}\). Niech \(w' = (k_1,\ldots,\, k_n)\). Pokażemy, że dla każdego \(i\) odpowiedni człon \(h_{k_i}\) w \(h_w = h_{k_1} \ldots h_{k_n}\) powstaje dokładnie z \(h_{k_i-1}\). Funkcja \(h\) jest różnowartościowa, a zatem nie istnieje żadne inne słowo \(x\), takie że \(h(x) = h_{k_i}\). Jeśli więc \(h_{k_i}\) nie powstaje z \(h_{k_i-1}\), to przekształcenie \(h(h_{m-1}) = h_m\) zamienia pewną cyfrę 1 w blok 10, który występuje na granicy wystąpienia \(h_{k_i}\) w \(h_m\), tzn. prawe 0 jest pierwszą cyfrą \(h_{k_i}\) lub lewe 1 jest ostatnią cyfrą \(h_{k_i}\). Ten pierwszy przypadek jest niemożliwy, bo \(h_{k_i}\) zaczyna się od 1.

Drugi przypadek może zajść jedynie wtedy, gdy po \(h_{k_i}\) występuje 0. Tak nie jest dla \(i < n\) (wówczas po \(h_{k_i}\) występuje \(h_{k_{i+1}}\)), ani dla \(i = n\) w przypadku, gdy \(h_w = h_{w'}\)1. Zatem musi być \(i = n\) oraz \(h_w = h_{w'}\), ale wtedy \(k_i \notin \lbrace 1,\, 3 \rbrace\), więc otrzymujemy sprzeczność.

Tym samym pokazaliśmy, że fragment \(h_{k_1} \ldots h_{k_n}\) w \(h_w\) jako podsłowie \(h_m\) powstaje w wyniku zastosowania przekształcenia \(h\) do \(h_{k_1-1} \ldots h_{k_n-1} = h_{w''}\). Zatem \(h_{w''}\) jest podsłowem \(h_{m-1}\), czyli \(w''\) jest dobry.

Pozostała do wykazania implikacja w drugą stronę. Jeżeli \(w''\) jest dobry, to istnieje takie \(m\), że \(h_{w''}\)0 lub \(h_{w''}\)1 jest podsłowem \(h_m\). Stąd \(h(h_{w''}\mathtt{0}) = h_{w'}\mathtt{1}\) lub \(h(h_{w''}\mathtt{1}) = h_{w'}\mathtt{10}\) jest podsłowem \(h_{m+1}\), a jedno i drugie zaczyna się od \(h_w\). Zatem \(w\) jest dobry.