8. Yvettin Ementál Neschopnosti vzorové riešenie

ahojxenianeuverisalepokazilsamimedzernik

jeeejtojesrandapodmesipisatbezmedzier

takdobrelendufamzetonebudenadmojementalneschopnosti

3
6
emental
mentalne
moj
moje
neschopnosti
schopnosti
4
korespondencny
seminar
z
programovania
4
aaa
aaab
bc
caaa

ano
nie
ano

Začnime jednoduchým pozorovaním: ak pre daný zoznam slov existujú nejaké dvojičky, určite existujú aj také dvojičky, ktoré začínajú rôznymi slovami, aj končia rôznymi slovami (túto vlastnosť budú spĺňať napríklad najkratšie dvojičky – ak by mali rovnaké prvé slovo, mohli by sme toto slovo vynechať a dostali by sme kratšie dvojičky, rovnako, ak by mali rovnaké posledné slovo). Na vyriešenie úlohy nám teda stačí zistiť, či existujú dvojičky, ktorých prvé aj posledné slová sú rôzne. Všetky algoritmy v tomto vzoráku budú hľadať práve takéto dvojičky.

Dvojičky by sme mohli konštruovať nasledujúcim postupom:

1. Nájdeme v zozname dve slová \(u, v\) také, že \(u\) je prefixom \(v\). Tieto dve slová si zapíšeme do dvoch riadkov (každé do jedného) tak, aby ich začiatky boli zarovnané pod seba. Platí teda, že ak sú dve písmená napísané nad sebou, sú to rovnaké písmená.

2. Kým platí, že naše riadky sú rôzne dlhé, robíme nasledujúci krok:

   2.1. Nájdeme v zozname nejaké vhodné slovo \(w\) a dopíšeme ho na koniec kratšieho riadka. Slovo \(w\) musí byť také, aby aj po jeho dopísaní platilo, že písmená, ktoré sú pod sebou, sú rovnaké.

3. Keď dospejeme k tomu, že oba riadky sú rovnako dlhé, našli sme dvojičky (slová, ktoré sme zapísali do prvého riadku, tvoria prvú z nich a slová, ktoré sme zapísali do druhého, tvoria druhú).

Pre zoznam slov {emental, mentalne, moj, moje, neschopnosti, schopnosti} by teda prvé tri kroky mohli vyzerať takto:

moj
moje

mojemental
moje

mojemental
mojementalne

Tento postup ešte nie je deterministický algoritmus – nie je jasné, ako máme zvoliť počiatočné slová \(u, v\), (ak by sme mali viac možností), ani ako máme v druhom kroku voliť slovo \(w\).

Platí však, že ak dvojičky existujú, pri vhodných voľbách \(u,v\) a \(w\) ich našim postupom vieme zostrojiť. Naopak, ak neexistujú, potom potom sa nám to pri žiadných voľbách \(u, v\) a \(w\) nepodarí (buď sa zasekneme na tom, že v zozname nie je vhodné slovo, alebo sa nikdy nedostaneme z druhého kroku). Na vyriešenie našej úlohy nám teda stačí zistiť, či existujú vhodné voľby slov zo zoznamu, ktoré by viedli k nájdeniu dvojičiek.

Všetky možnosti volieb \(u, v\) a \(w\), vyskúšať nevieme, lebo ich môže byť nekonečne veľa (napríklad pre zoznam slov {c, ca, aa, ab, ba bb} sa náš postup v druhom kroku zacyklí, pričom si vždy môže vybrať z dvoch možných \(w\)). Namiesto toho založíme naše riešenie na nasledujúcich pozorovaniach.

To, či je v nejakom momente nášho postupu ešte možné doplniť naše dva riadky na dvojičky, závisí iba na rozdieli našich riadkov, teda na postupnosti písmen, o ktorú je dlhší riadok dlhší. Tento rozdiel si nazvime stav. Ak sme napríklad zatiaľ napísali

mojemental
moje

povieme, že sme v stave "mental". Môžeme si všimnúť, že každý stav, od ktorého sa môžeme dostať, je sufixom nejakého slova zo zoznamu. To znamená, že rôznych možných stavov je \(O(n)\).

Na celú úlohu sa môžeme pozerať ako na grafový problém: vrcholy sú stavy a hrana zo stavu \(A\) do stavu \(B\) vedie práve vtedy, keď v zozname existuje slovo \(w\), ktorého napísaním by sme sa dostali zo stavu \(A\) do stavu \(B\). Tie stavy, do ktorých sa dá dostať prvým krokom nášho postupu, nazvime začiatočné. Naším cieľom je zistiť, či sa z nejakého začiatočného stavu dá dostať do stavu "" (prázdny reťazec), keďže tento stav zodpovedá tomu, že naše dva riadky sú rovnako dlhé.

Prvé riešenie

Na grafe stavov urobíme prehľadávanie do šírky. Graf si nebudeme konštruovať explicitne, ale podľa potreby za behu. Budeme si udržiavať množinu stavov, do ktorých sa dá dostať, ako množinu reťazcov. Okrem toho budeme mať aj frontu stavov, do ktorých sa dá dostať a ešte sme sa z nich nešírili.

Pre dvojicu slov \(x, y\) takú, že \(x\) je prefix \(y\), budeme notáciou \(y - x\) značiť slovo, ktoré dostaneme, keď zo slova \(y\) zmažeme prefix \(x\).

Na začiatku sa pre každú dvojicu slov \(u, v\) zo zoznamu pozrieme, či \(u\) nie je prefixom \(v\). Ak je, pridáme do množiny dosiahnuteľných stavov, aj do fronty, slovo \(v - u\). Týmto sme našli všetky začiatočné stavy.

Následne vyberáme stavy z fronty a z každého z nich sa šírime. Keď vyberieme z fronty nejaký stav \(s\), prejdeme celý zoznam slov a hľadáme v ňom také, ktorým je \(s\) prefixom, prípadne ktoré sú prefixom \(s\).

• Keď nájdeme nejaké slovo \(w\), ktorého je \(s\) prefixom, znamená to, že zo stavu \(s\) sa dá ísť do stavu \(w - s\).
• Keď nájdeme nejaké slovo \(w\), ktoré je prefixom \(s\), znamená to, že z \(s\) sa dá ísť do \(s - w\).

V oboch prípadoch sa pozrieme, či tento nový stav (teda \(w - s\), alebo \(s - w\)) už máme v množine objavených stavov. Ak nie, pridáme ho tam a pridáme ho aj do fronty nerozšírených stavov.

Takto pokračujeme, až kým sa nám nevyprázdni fronta, alebo kým neobjavíme stav "" (prázdny reťazec). Dvojičky existujú práve vtedy, ak sme počas prehľadávania objavili stav "".

Tento algoritmus prehľadá graf stavov korektne, keďže ide iba o jemne exotickú implementáciu prehľadávania do šírky.

Zložitosť

Pri hľadaní začiatočných stavov porovnávame každé slovo \(v\) zo zoznamu s každým možným slovom \(u\). Slová v zozname sú dokopy dlhé \(n\), pre jedno \(v\) teda toto porovnávanie teda zaberie \(O(n)\) času. Pri porovnávaní nájdeme pre jedno \(v\) nanajvýš \(k\) vhodných slov \(u\), pre ktoré vznikne začiatočný stav \(v - u\). Každý z týchto začiatočných stavov je dlhý \(O(n)\) a treba ho pridať (ak tam ešte nie je) do množiny dosiahnuteľných stavov, ktorá obsahuje \(O(n)\) reťazcov dlhých \(O(n)\). Ak množinu stavov implementujeme pomocou vyváženého vyhľadávacieho stromu (ako napríklad std::set<std::string> v C++), jedno vyhľadávanie/vkladanie do nej bude vyžadovať \(O(\log n)\) porovnaní trvajúcich \(O(n)\). To znamená, že pridávanie jedného začiatočného stavu (resp. kontrola, že už bol objavený) trvá \(O(n \log n)\). Pridanie všetkých začiatočných stavov objavených pri danom \(v\) teda bude trvať \(O(kn \log n)\). Jedno \(v\) teda spacujeme v čase \(O(kn \log n + n) = O(kn \log n)\). Všetky \(v\) nám budú trvať \(O(k^2n \log n)\).

Pri rozširovaní sa z nejakého stavu \(s\) je situácia podobná: musíme porovnať \(s\) s každým možným \(w\), čo nám zaberie \(O(n)\) času. Pritom nájdeme \(O(k)\) hrán, pre každú z nich musíme overiť, či sa nejaký nový stav dlhý \(O(n)\) nachádza v množine objavených. To zaberie dokopy \(O(kn \log n)\). Na rozšírenie jedného stavu teda minieme \(O(kn \log n + n) = O(kn \log n)\) času. Keďže možných stavov je \(O(n)\), dokopy sa budeme rozširovať \(O(n)\)-krát, teda naše prehľadávanie do šírky bude trvať \(O(kn^2 \log n)\).

Keďže \(k \leq n\), časová zložitosť celého algoritmu je \(O((kn^2 \log n) + (k^2n \log n)) = O(kn^2 \log n)\). Ak by sme množinu stavov implementovali efektívnejšou dátovou štruktúrou, napríklad písmenkovým stromom, zložitosť by bola \(O(kn^2)\) (keďže v písmenkovom strome vieme slová dĺžky \(n\) vyhľadávať/pridávať v \(O(n)\)). Trochu náročnejšou analýzou sa dá náš odhad zložitosti ešte spresniť na \(\Theta\left(n^2 \min\left(k, \sqrt{n}\right)\right)\).

Lepšia reprezentácia stavov

Predošlé riešenie sa dá zrýchliť šikovnejšou reprezentáciou stavov. Vieme, že každý dosiahnuteľný stav je sufixom nejakého slova zo zoznamu. Dá sa teda popísať dvojicou čísel \((i, l)\), kde \(i\) je index nejakého slova v zozname a \(l\) je dĺžka sufixu.

Všetky operácie, ktoré so stavmi v našom algoritme robíme, vieme efektívne robiť aj s takouto reprezentáciou. Pri hľadaní začiatočných stavov vždy vieme, z ktorých slov \(u, v\) jednotlivé stavy vznikajú. To znamená, že pre ne vieme v konštantnom čase vypočítať ich reprezentáciu. Pri šírení sa z nejakého stavu \((i, l)\) si skonštruujeme príslušný reťazec (sufix \(i\)-teho slova dlhý \(l\)) a ten porovnávame so slovami v zozname. Vždy, keď nájdeme nejakú hranu, vieme aj v konštantnom čase vypočítať reprezentáciu stavu, do ktorého vedie (keďže vieme, z akého slova daný stav vznikne).

Na reprezentáciu množiny dosiahnuteľných stavov nám stačí pamätať si pre každé slovo \(t\) zo zoznamu jedno pole boolovských premenných rovnako dlhé ako \(t\). Na \(l\)-tom indexe v tomto poli si budeme pamätať, či je stav zodpovedajúci sufixu slova \(t\) dĺžky \(l\) dosiahnuteľný. Keďže slová zo zoznamu sú dohromady dlhé \(n\), celková dĺžka týchto boolovských polí bude tiež \(n\). Overenie, či je nejaký stav v množine dosiahnuteľných, teraz vieme urobiť v čase \(O(1)\), rovnako aj pridanie stavu do množiny dosiahnuteľných.

Všimnime si, že graf, ktorý teraz prehľadávame, je trochu iný, ako v predošlom riešení. Ak totiž dve slová zo zoznamu majú spoločný sufix, stav zodpovedajúci tomuto sufixu má až dve možné reprezentácie a my s ním pracujeme, akoby to boli dva rôzne vrcholy. Dá sa však ľahko ukázať, že cesta zo začiatočného stavu do stavu "" (prázdneho reťazca) existuje v našom grafe práve vtedy, keď existovala aj v pôvodnom. Navyše, pre náš upravený graf stále platí, že má \(O(n)\) vrcholov.

Časovú zložitosť tohto riešenia odhadneme rovnakým spôsobom, ako pri predošlom riešení. Keďže sme výrazne zrýchlili operácie s množinou dosiahnuteľných stavov, časová zložitosť sa nám zlepší na \(O(n^2)\).

Rýchlejšie hľadanie hrán

V doterajších riešeniach sme si hrany nášho grafu konštruovali počas prehľadávania, podľa potreby. Skúsme si ich teraz explicitne skonštruovať vopred. Pre každý sufix \(s\) každého slova zo zoznamu teda potrebujeme nájsť všetky slová \(w\), také, že \(s\) je prefixom \(w\), alebo \(w\) je prefixom \(s\). Ak by sme to robili naivne, trvalo by nám to \(O(n^2)\). Ide to však aj rýchlejšie, s pomocou Knuth-Morris-Prattovho algoritmu¹.

Pre každú dvojicu slov \(x, w\) zo zoznamu spustíme KMP s textom \(x\) a vzorkou \(w\). Ak je \(w\) kratšie než \(x\), možno nájdeme niekoľko výskytov \(w\) v \(x\). Každý z týchto výskytov vlastne znamená, že slovo \(w\) je prefixom nejakého sufixu \(s\) slova \(x\). Príslušné hrany pridáme do grafu.

KMP si počas svojho behu udržiava informáciu o tom, aký najdlhší sufix prečítanej časti textu je zároveň prefixom vzorky. To znamená, že po dočítaní celého slova \(x\) budeme vedieť, aký najdlhší sufix slova \(x\) je zároveň prefixom slova \(w\). Príslušnú hranu pridáme do grafu. Okrem toho potrebujeme nájsť aj všetky ostatné sufixy \(x\), ktoré sú prefixami \(w\). Tie vieme nájsť v čase lineárnom od ich počtu, s využitím informácie, ktorú sme si predrátali v rámci KMP – stačí nám nasledovať spätné linky (to, čo v texte v Kuchárke voláme funkcia \(\mathrm{next}()\)).

Takto sme našli všetky hrany zo sufixov slova \(x\), ktoré využívajú slovo \(w\), pričom nám to trvalo \(O(|x| + |w|)\) času. Keď tento výpočet urobíme pre každú dvojicu \(x, w\), budeme mať skonštruované všetky hrany v grafe. Dokopy spustíme KMP \(k^2\)-krát, pričom každé slovo zo zoznamu bude \(k\)-krát v roli slova \(x\) a \(k\)-krát v roli slova \(w\). Každé slovo \(y\) teda do časovej zložitosti prispeje časom \(O(k|y|)\). Keďže súčet dĺžok slov je \(n\), celková časová zložitosť konštruovania grafu bude \(O(kn)\).

Na hľadanie začiatočných vrcholov môžeme využiť náš čerstvo zostrojený graf. Pre každé slovo \(v\) zo zoznamu sa pozrieme na stav, ktorý zodpovedá jeho najdlhšiemu sufixu (teda celému slovu \(v\)). Z tohto stavu povedie niekoľko hrán, pričom jedna pôjde do stavu "" (prázdny reťazec). Všetky ostatné hradny vedú do začiatočných stavov. Rozmyslite si, že takto nájdeme všetky začiatočné stavy (dokonca každý dvakrát).

Keďže náš graf má \(O(n)\) vrcholov a z každého vedie nanajvýš \(k\) hrán, prehľadávanie grafu bude trvať \(O(kn)\), teda celý algoritmus nám beží v čase \(O(kn)\). Ak by sme chceli odhadnúť zložitosť nášho algoritmu iba v závislosti od \(n\), môžeme využiť, že \(k \leq n\), teda náš algoritmus beží v čase \(O(n^2)\). V skutočnosti sa však počet slov dá odhadnúť aj tesnejšie: keďže všetky slová musia byť rôzne, bude ich nanajvýš \(O(\frac{n}{\log n})\), teda náš algoritmus beží v čase \(O\left(\frac{n^2}{\log n}\right)\).

Počet hrán v grafe

Graf, ktorý sme v predošlom algoritme zostrojili, mal \(O(n)\) vrcholov a mohol mať až rádovo \(\frac{n^2}{\log n}\) hrán. Naozaj sa pritom dajú zostrojiť vstupy, pre ktoré bude mať graf \(\Theta\left(\frac{n^2}{\log n}\right)\) hrán. Zdá sa teda, že naše riešenie sa už nedá zlepšiť.

V skutočnosti však všetky “zlé” vstupy, pre ktoré má graf veľa hrán, využívajú fakt, že ak má veľa slov rovnaký sufix a veľa iných slov má taký prefix, v grafe sa pospájajú “každé s každým”. Ak prejdeme naspäť ku grafu, kde každý reťazec mohol mať iba jeden vrchol (bez ohľadu na počet slov, ktorých je sufixom), najväčší možný počet hrán sa výrazne zníži.

Najprv potrebujeme zmeniť spôsob, ako reprezentujeme vrcholy grafu. Všetky slová zo zoznamu si napíšme odzadu. Nad takýmito odzadu napísanými slovami teraz postavme písmenkový strom. Každý vrchol písmenkového stromu zodpovedá nejakému reťazcu, z ktorého po otočení dostaneme sufix jedného, alebo viacerých slov zo zoznamu. Zároveň každý vrchol písmenkového stromu zodpovedá inému reťazcu. Vrcholy písmenkového stromu nám teda dobre reprezentujú stavy, pričom každý možný stav je reprezentovaný práve raz.

Koľko hrán môže mať náš graf teraz? Hrany si rozdeľme na dva typy:

• vnútorné hrany sú také, ktoré vznikli zo stavu \(s\) s použitím slova \(w\) kratšieho než \(s\) a vedú do stavu \(s - w\).
• vonkajšie hrany sú také, ktoré vznikli zo stavu \(s\) s použitím slova \(w\) dlhšieho (alebo rovnako dlhého) ako \(s\) a vedú do stavu \(w - s\).

Keď sa pozrieme na nejaký konkrétny stav \(s\), vedie z neho toľko vnútorných hrán, koľko je v zozname slov, ktoré sú prefixom \(s\). Všetky tieto slová sú určite rôzne (lebo slová v zozname sú rôzne) a tým pádom rôzne dlhé (lebo rôzne prefixy slova \(s\) musia byť rôzne dlhé). Keďže slová v zozname sú dokopy dlhé \(n\), rôzne dlhých slov v ňom môže byť nanajvýš \(O\left(\sqrt{n}\right)\). To znamená, že z každého vrcholu vedie nanajvýš \(O\left(\sqrt{n}\right)\) vnútorných hrán. Zároveň platí, že ich z každého vrcholu vedie nanajvýš \(k\). Celkový počet vnútorných hrán je teda \(O\left(n \min\left(\sqrt{n}, k\right)\right)\).

Vezmime si teraz nejaké číslo \(l\) a pozrime sa na všetky stavy dĺžky \(l\) (v hĺbke \(l\) v našom písmenkovom strome). Tieto stavy budeme volať stavy \(l\)-tej úrovne. Počet vonkajších hrán vedúcich zo stavov \(l\)-tej úrovne označme \(o_l\). Na to, aby z nejakého stavu \(s\) z \(l\)-tej úrovne viedla nejaká vonkajšia hrana, musí v zozname existovať nejaké slovo \(w\) také, že \(s\) je prefixom \(w\). Keďže každé slovo má nanajvýš jeden prefix dĺžky \(l\), každé slovo zo zoznamu môže byť v roli \(w\) pre nanajvýš jeden zo stavov \(l\)-tej úrovne. Platí teda \(o_l \leq k\). Ba čo viac, v roli \(w\) môžu byť iba slová dlhé aspoň \(l\). Ak si počet slov zo zoznamu, dlhých aspoň \(l\), označíme ako \(k_l\), platí \(o_l \leq k_l\).

Počet vonkajších hrán v našom grafe vieme spočítať ako

\[o_1 + o_2 + \dots + o_n\text{.}\]

Vieme pritom, že platí

\[o_1 + o_2 + \dots + o_n \leq k_1 + k_2 + \dots + k_n\text{.}\]

Navyše platí

\[k_1 + k_2 + \dots + k_n = n\text{,}\]

keďže každé slovo je zarátané v práve toľkých \(k_i\), koľko má písmen. Vonkajších hrán je teda nanajvýš \(n\). Dokopy má teda náš graf \(O\left(n \min\left(\sqrt{n}, k\right)\right)\) hrán.

Ešte rýchlejšie hľadanie hrán

Náš nový graf je redší, bude sa teda dať rýchlejšie prehľadať. Hľadanie hrán nám však stále trvá \(\Theta(nk)\) času. To sa dá zrýchliť tým, že namiesto spúšťania KMP \(k^2\)-krát, použijeme Aho-Corasickovej algoritmus, ktorý bude stačiť spustiť \(k\)-krát.

Vo všetkých behoch Aho-Corasickovej algoritmu budeme používať rovnakú množinu vzoriek: všetky slová zo zoznamu. Predrátanie potrebných informácií pre vzorky (písmenkového stromu so spätnými linkami) nám teda stačí urobiť len raz. V tomto momente v našom algoritme vystupujú dva písmenkové stromy – jeden nad obrátenými slovami zo zoznamu, ktorého vrcholy sú zároveň vrcholmi grafu, ktorý budujeme, a druhý nad pôvodnými slovami zo zoznamu, využívaný v Aho-Corasickovej algoritme.

Pre každé slovo \(x\) zo zoznamu spustíme Aho-Corasickovej algoritmus s textom \(x\) a celým zoznamom slov ako vzorkami. Vždy, keď Aho-Corasickovej algoritmus nájde výskyt nejakého slova v slove \(x\), pridáme do grafu príslušnú vnútornú hranu. Keď Aho-Corasickovej algoritmus dočíta celé \(x\), budeme vedieť, aký najdlhší sufix slova \(x\) je prefixom jedného, alebo viacerých slov zo zoznamu. Tento sufix označme \(t\). Nájdeme všetky slová zo zoznamu, ktorých prefixom je \(t\) (o chvíľu si ukážeme ako) a príslušné vonkajšie hrany pridáme do grafu. Následne nájdeme druhý najdlhší sufix \(x\), ktorý je prefixom nejakých slov zo zoznamu (v konštantnom čase, nasledovaním spätnej linky v Aho-Corasickovej strome) a urobíme preň to isté. Takto pokračujeme, až kým nenastane jedna z dvoch možností:

1. Prešli sme všetky zaujímavé sufixy slova \(x\). V tomto momente sú všetky hrany, ktoré vedú zo sufixov \(x\), objavené.
2. Prišli sme na nejaký sufix \(s\), ktorý je zároveň sufixom nejakého iného, už spracovaného slova. To znamená, že hrany vedúce zo stavu \(s\), aj všetkých kratších sufixov slova \(x\) sú už objavené a spracovávanie slova \(x\) môžeme ukončiť.

Je dôležité, že v druhom prípade ihneď prestaneme pracovať. Inak by sme mohli vonkajšie hrany vedúce z jedného stavu objavovať veľakrát a vôbec by nám nepomohlo, že graf, ktorý konštruujeme, je riedky. Pri pridávaní vnútorných hrán tiež môžeme kontrolovať, či pridávaná hrana neviedie zo skôr spracovaného stavu, aby sme sa vyhli duplicitnému pridávaniu hrán (pri analýze zložitosti budeme predpokladať, že to kontrolujeme. Zložitosť by sa však nezhoršila, ani keby sme to pre vnútorné hrany nerobili).

Zostáva vymyslieť, ako pre zadaný reťazec \(t\) nájsť všetky slová zo zoznamu, ktorých je prefixom. Reťazcu \(t\) zodpovedá vrchol v Aho-Corasickovej strome. Všetkým slovám zo zoznamu, pre ktoré je \(t\) prefixom, zodpovedajú nejaké vrcholy Aho-Corasickovej stromu, ktoré sú v podstrome pod \(t\). Stačí nám teda tento podstrom prehľadať (napríklad do hĺbky) a nájsť v ňom všetky vrcholy, ktoré zodpovedajú celému slovu zo zoznamu. Pritom si treba dať pozor na to, že podstrom pod \(t\) môže byť veľký, aj keby v ňom bolo iba jedno slovo. V takom prípade si ho nemôžeme dovoliť prehľadávať naivne, lebo by to trvalo veľmi dlho.

Preto urobíme takzvanú kompresiu ciest. Vrchol Aho-Corasickovej stromu budeme považovať za zaujímavý, ak má aspoň jednu z týchto dvoch vlastností:

• Končí v ňom nejaké slovo zo zoznamu
• Má aspoň dve deti

Nezaujímavé vrcholy sú teda také, v ktorých nekončí žiadne slovo a majú práve jedno dieťa. Pre každý nezaujímavý vrchol \(V\) si na začiatku algoritmu predpočítame, do akého prvého zaujímavého vrcholu \(U\) prídeme, ak z vrcholu \(V\) pôjdeme po strome nadol. Keďže z nezaujímavých vrcholov sa dá ísť nadol vždy práve jedným spôsobom, vrchol \(U\) je jednoznačne určený. Toto predrátanie vieme urobiť v čase \(O(n)\), šikovným prehľadávaním do hĺbky. Následne vždy, keď pri prehľadávaní nejakého podstromu Aho-Corasickovej stromu prídeme do nejakého nezaujímavého vrcholu, skočíme rovno do najbližšieho zaujímavého vrcholu. Takto zaručíme, že čas prehľadávania podstromu bude lineárny od počtu nájdených slov, keďže prehľadáme nanajvýš toľko nezaujímavých vrcholov, ako zaujímavých a v minimálne polovici zaujímavých vrcholov končia slová (to vyplýva z toho, že strom má viac listov, než vetvení).

Zložitosť

Na začiatku si potrebujeme vybudovať oba naše písmenkové stromy a predpočítať si na nich všetko potrebné. To nám zaberie \(O(n)\) času. Následne spúšťame Aho-Corasickovej algoritmus, ktorý musí postupne prečítať texty s celkovou dĺžkou \(n\). Samotné čítanie mu teda zaberie \(O(n)\) času. Okrem čítania slov ale robíme aj iné činnosti: pridávame vnútorné hrany a hľadáme a prídávame vonkajšie hrany. Všimnime si, že všetky činnosti, súvisiace s pridávaním hrán, mali časovú zložitosť lineárnu od počtu nových hrán, ktoré pridali do grafu. Keďže graf má \(O\left(n \min\left(\sqrt{n}, k\right)\right)\) hrán, činnosti súvisiace s pridávaním hrán zaberú dohromady \(O\left(n \min\left(\sqrt{n}, k\right)\right)\) času. Nakoniec ešte náš graf v čase \(O\left(n \min\left(\sqrt{n}, k\right)\right)\) prehľadáme. Celková časová zložitosť nášho algoritmu je teda \(O\left(n \min\left(\sqrt{n}, k\right)\right)\). Ak ju vyjadríme bez použitia \(k\), dostaneme \(O\left(n \sqrt{n}\right)\).