Zadanie
Yvette sa na klávesnici pokazil medzerník. Hneď o tom aj napísala svojej kamarátke Xénii. Samozrejme, v rámci dobrých zvykov, bez diakritiky, interpunkcie a veľkých písmen:
ahojxenianeuverisalepokazilsamimedzernik
Lúštenie tejto správy Xénii chvíľku trvalo, no celkom sa jej to zapáčilo. Odpísala teda:
jeeejtojesrandapodmesipisatbezmedzier
Yvette lúštenie správy spočiatku veľmi nešlo. “To je nad moje mentálne schopnosti,” pomyslela si. Nakoniec však správu rozlúštila, a keďže nechcela Xéniu sklamať, odpovedala:
takdobrelendufamzetonebudenadmojementalneschopnosti
Táto správa Xéniu úprimne zmiatla. “Nad môj Ementál Neschopnosti? Čo to je? Už som počula o Prsteni Neviditeľnosti, Opasku Sily, aj Papučiach Obratnosti, ale o Ementáli Neschopnosti som ešte nepočula.”
Po chvíli zmätku a dvoch telefonátoch dievčatá pochopili, že ak si budú písať bez medzier, občas sa nejaká správa bude dať rozdeliť na slová viacerými spôsobmi. Preto sa rozhodli, že pri písaní budú používať iba obmedzenú množinu slov, tak, aby sa im toto nemohlo stať. Ako však zistiť, či je nejaká množina slov dobrá?
Úloha
Majme zoznam \(k\) rôznych slov. Dve rôzne postupnosti slov zo zoznamu budeme volať dvojičky, ak zreťazením slov z jednej postupnosti vznikne rovnaký reťazec ako zreťazením slov druhej postupnosti. Napríklad, ak by náš zoznam obsahoval slová {emental
, mentalne
, moj
, moje
, neschopnosti
, schopnosti
}, postupnosti (moje
, mentalne
, schopnosti
) a (moj
, emental
, neschopnosti
) sú dvojičky. Slová sa môžu v rámci postupností aj opakovať, postupnosti však musia byť rôžne. Teda napríklad postupnosť (moje
, mentalne
, schopnosti
, moje
, moje
) je dvojička s postupnosťou (moj
, emental
, neschopnosti
, moje
, moje
), ale postupnosti (moj
, moje
) a (moj
, moje
) dvojičky nie sú, lebo nie sú rôzne.
Vašou úlohou bude pre zadaný zoznam slov rozhodnúť, či preň existujú nejaké dvojičky.
Formát vstupu
Aby sme vám sťažili náhodné hádanie správnych odpovedí, v jednom vstupnom súbore bude niekoľko zadaní úlohy.
V prvom riadku bude jedno celé číslo \(t\) (\(1 \leq t \leq 10\)) – počet zadaní, ktoré máte vyriešiť. Ďalej je na vstupe \(t\) zadaní, každé z nich má nasledujúci formát.
V prvom riadku zadania je jedno celé číslo \(k\) (\(1 \leq k \leq 200,000\)) – počet slov v zozname. Nasleduje \(k\) riadkov, každý z nich obsahuje jeden neprázdny reťazec tvorený malými písmenami anglickej abecedy (a
-z
) – jedno slovo zo zoznamu. Všetky tieto slová sú navzájom rôzne.
Súčet dĺžok všetkých slov vo vstupnom súbore (teda zo všetkých \(t\) zadaní dokopy) označme \(N\). Bude platiť \(N \leq 200,000\).
Formát výstupu
Pre každé zadanie zo vstupu vypíšte (v rovnakom poradí) jeden riadok. Ak pre zadaný zoznam slov existujú dvojičky, riadok nech obsahuje iba slovo ano
, ak neexistujú, riadok nech obsahuje iba slovo nie
.
Hodnotenie
Vaše programy budeme testovať na štyroch skupinách testovacích vstupov. Pre jednotlivé skupiny budú platiť nasledujúce obmedzenia:
Skupina | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1\leq N\leq\) | \(100\) | \(2\,000\) | \(200\,000\) | \(200\,000\) |
\(1\leq k\leq\) | \(20\) | \(100\) | \(100\) | \(200\,000\) |
Súčet dĺžok všetkých slov v jednom zadaní označme \(n\). Vo vašich riešeniach uvádzajte časovú zložitosť vášho algoritmu v závislosti od parametrov \(n\) (celková dĺžka slov v zozname) a \(k\) (počet slov v zozname), teda nie od parametrov \(t\) a \(N\).
Okrem toho uveďte aj odhad časovej zložitosti vášho algoritmu iba v závislosti od parametra \(n\). Ak by teda napríklad váš algoritmus bežal v čase \(O(n^2k^3)\), môžete uviesť, že beží v čase \(O(n^5)\) (keďže \(k \leq n\) na každom vstupe).
Príklad
Input:
3
6
emental
mentalne
moj
moje
neschopnosti
schopnosti
4
korespondencny
seminar
z
programovania
4
aaa
aaab
bc
caaa
Output:
ano
nie
ano
Najkratšie dvojičky v poslednom zadaní sú postupnosti (aaab
, caaa
) a (aaa
, bc
, aaa
).
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:
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á.
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é.
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 algoritmu1.
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í:
- Prešli sme všetky zaujímavé sufixy slova \(x\). V tomto momente sú všetky hrany, ktoré vedú zo sufixov \(x\), objavené.
- 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)\).
Ak tento algoritmus nepoznáte, odporúčam v tomto momente prerušiť čítanie tohto vzoráku a prečítať si o ňom niečo. Zvyšok tohto vzoráku predpokladá, že KMP poznáte.↩︎
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.