7. Ozajstné vzrušenie vzorové riešenie

abcaabbabaa
3
aab
ba
ba

neviem

xxyyzzxyzxyz
2
yyzz
zz

zabludil

cbaxxxxabcdefxxxxccbbaa
2
abc
xx

z Bratislavy do Kosic

Zamyslime sa nad tým, ako by mohol Zdeno sám overiť, ktorým smerom mohol cestovať. Zaoberajme sa len cestou z Bratislavy do Košíc, cestu opačným smerom overíme analogicky. Zdeno môže postupovať nasledovne: začne v Bratislave, a pôjde smerom do Košíc. Pritom si postupne vyškrtáva úseky, ktoré už videl – vždy, keď vlak prejde časť cesty reprezentovanú jedným znakom, tak Zdeno overí, či práve nedopozeral aktuálne overovaný úsek. Ak áno, tak si ho zaškrtne (nakoľko nič nestratí tým, že ho zaškrtne najskôr, ako vie), a začne overovať nasledujúci úsek.

Zamyslime sa teraz nad tým, ako môže Zdeno overovať, či práve nedopozeral aktuálny úsek. Jeho reťazec si označíme \(B\) a jeho znaky si postupne označíme \(B_1, B_2, \ldots, B_{|B|}\). Reťazec reprezentujúci cestu z Bratislavy do Košíc si označíme \(A\), a jeho znaky postupne \(A_1, A_2, \ldots, A_{|A|}\). Aktuálnu pozíciu vlaku označíme \(i\).

Riešenie hrubou silou

Uvedomíme si, čo chceme zistiť. To, či Zdeno dopozeral \(B\), znamená presne to, že reťazec posledných videných \(|B|\) znakov je rovný \(B\). Formálne, je to ekvivalentné tomu, že \(B = A_{i-|B|+1} A_{i-|B|+2} \ldots A_{i-1} A_i\). A to vieme overiť jedným prechodom – najprv overíme, či \(A_i = B_{|B|}\). Ak nie, tak Zdeno \(B\) nemohol dopozerať, a skončíme. Ak áno, tak overíme \(A_{i-1} = B_{|B|-1}\), ak aj to platí, tak overíme \(A_{i-2} = B_{|B|-2}\), a tak ďalej, až po posledný znak. Ak sme nenašli žiaden rozdiel, Zdeno práve dopozeral \(B\).

Zamyslime sa nad časovou zložitosťou tohto algoritmu. Na jednej pozícii \(i\) môžeme potrebovať overiť až \(O(|B|)\) znakov. Dokopy môže Zdeno spraviť až \(O|A|\cdot |B|)\) operácií – presnejšie \(O(d \cdot |B|)\), kde \(d\) je vzdialenosť prejdená vlakom, kým Zdeno nenájde pozíciu, kde končí hľadaný úsek. A naozaj existuje vstup, na ktorom ich toľko spraví – napríklad \(A = aaaaaa \ldots a\) a \(B = aaaa \ldots aaab\).

Všimnime si, že náš algoritmus v skutočnosti robí nasledovné: zistí, aký najdlhší sufix \(B\) končí na pozícii \(i\)¹. Keď ale Zdeno uvidí nový znak, tak nevieme jednoducho z predchádzajúceho najdlhšieho sufixu povedať, aký bude najdlhší sufix teraz.

Skoro algoritmus KMP

Čo keby sme sa ale nepozerali na najdlhší sufix, ale najdlhší prefix \(B\) končiaci na pozícii \(i\)? Z takej informácie tiež vieme ľahko overiť, či Zdeno práve dopozeral \(B\) – vtedy je najdlhší prefix dlhý \(|B|\).

Predpokladajme, že poznáme najdlhší prefix končiaci na pozícii \(i\). Označme jeho začiatok \(l_1\). (Potom je tento najdlhší prefix dlhý \(i+1-l_1\).) Zamyslime sa nad tým, ako by sme vedeli zistiť najdlhší prefix končiaci na \(i+1\). Na to nám stačí zistiť jeho začiatok \(l_2\) – takže hľadáme najmenšie \(k\) také, že \(A_k A_{k+1} \ldots A_i A_{i+1}\) je prefixom \(B\). (Potom \(l_2 = k\).) Keďže \(A_{l_2} A_{l_2+1} \ldots A_i A_{i+1}\) je prefixom \(B\), tak aj \(A_{l_2} A_{l_2 + 1} \ldots A_i\) je prefixom \(B\). Preto je najviac taký dlhý, ako prefix začínajúci na \(l_1\) a končiaci na \(i\), ktorý je najdlhší možný končiaci v \(i\). Takže nový prefix, končiaci v \(i+1\) nemôže začínať skôr ako na pozícii \(l_1\), kde začína \(A_{l_1} A_{l_1 + 1} \ldots A_i\). Teda musí platiť \(l_2 \geq l_1\).

Potom nám stačí overovať, či pridaním znaku \(A_{i+1}\) na koniec predĺžime starý prefix. Ak áno, tak sme našli najdlhší prefix \(B\) končiaci na \(i+1\) (teda platí \(l_2 = l_1\)). Ak nie, tak vyskúšame \(k = l_1+1\), ak ani to nevyhovuje, tak vyskúšame \(k = l_1+2\), a tak ďalej. Pri overovaní nového \(k\) musíme porovnať \(i-k+1\) znakov prefixu \(B\), či sa zhodujú so znakmi \(A_k \dots A_i\).

Zamyslime sa nad časovou zložitosťou. Ak sa nám podarilo starý prefix predĺžiť, tak sme spravili len 1 porovnanie. V opačnom prípade sme pri každom posune \(k\) spravili najviac \(O(|B|)\) porovnaní. \(k\) posúvame vždy len doprava (zvyšuje sa), a týchto posunov môže byť najviac \(|A|\), alebo \(d\) – vzdialenosť prejdená vlakom, kým Zdeno nenájde pozíciu. Takže celková časová zložitosť môže byť najviac \(O(|A| \cdot |B|)\), resp. \(O(d \cdot |B|)\). Vyzerá to teda tak, že sme si veľmi nepomohli…

Algoritmus KMP

V predošlej časti sme zistili, že ak si pamätáme najdlhší prefix \(B\), ktorý končí na pozícii \(i\), občas vieme rýchlo nájsť prefix \(B\) končiaci na \(i+1\) – ak je znak \(A_{i+1}\) ďalším znakom v \(B\). Ak ale \(A_{l_1} A_{l_1 + 1} \ldots A_{i+1}\) nie je prefixom \(B\), potrebujeme zistiť, kde má začínať najdlhší prefix \(B\) končiaci na pozícii \(i+1\). Teraz si ukážeme, ako program vylepšiť tak, aby sme pre \(l_2\) nemuseli skúšať všetky hodnoty \(l_1+1, l_1+2, \dots, i+1\) ale len tie, ktoré by veľmi pravdepodobne mohli byť začiatkami nejakého prefixu \(B\) – začiatky druhého najdlhšieho, tretieho najdlhšieho, … prefixu \(B\), ktorý končí v \(i\).

Zopakujme si, že \(l_2\) má nasledujúce vlastnosti: \(l_2 \geq l_1\). \(P_2 = A_{l_2} A_{l_2+1} \ldots A_i\) je prefixom \(B\) a \(P_1 = A_{l_1} A_{l_1+1} \ldots A_i\) je tiež prefixom \(B\). Potom \(P_2\) je sufixom \(P_1\). Takže by nám stačilo skúšať také \(k\), pre ktoré \(A_k A_{k+1} \ldots A_i\) je sufixom \(P_1\) (a zároveň prefixom \(B\)). Označme si všetky takéto \(k\) od najmenšieho postupne \(l_1 = k_1 < k_2 < \ldots < k_K\). Všimneme si, že \(A_{k_2} A_{k_2+1} \ldots A_i\) je najdlhší sufix \(A_{k_1} A_{k_1+1} \ldots A_i\), ktorý je aj prefixom \(B\). Podobne pre \(k_3\) a \(k_2\), \(k_4\) a \(k_3\), a tak ďalej až po \(k_K\) a \(k_{K-1}\).

Ak by sme vedeli pre každý prefix \(B\), označme ho \(P\), zistiť jeho najdlhší vlastný (rôzny od \(P\)) sufix taký, že je tiež prefixom \(B\), tak by sme našu postupnosť vedeli ľahko zostrojiť:

Nech \(P\) je prefix \(B\) a \(suf(P)\) je najdlhší vlastný sufix \(P\). Naša postupnosť možných začiatkov prefixov \(B\) – \(k_1 < k_2 < \ldots < k_K\) – je potom: \[l_1 = i - |P| + 1,~ i-|suf(P)|+1,~ i-|suf(suf(P))|+1,~ \ldots,~ i+1\]

Ak sa nám podarí tieto sufixy prefixov \(B\) spočítať, program si bude pre každú overovanú pozíciu \(i\) v \(A\) pamätať \(P_i\) – najdlhší prefix \(B\) končiaci v \(i\). Keď chceme zistiť najdlhší prefix končiaci na pozícii \(i+1\):

• Ak bude ďalšie písmenko v \(A\) dobré (teda rovnaké ako ďalšie písmenko v \(B\), formálne \(A_{i+1} = B_{|P_i|+1}\)), \(P_{i+1}\) bude o 1 dlhší prefix \(B\) ako \(P_i\).
• Ak bude ďalšie písmenko v \(A\) zlé, skúsime sa pozrieť, či toto písmenko \(A_{i+1}\) nepasuje za prefix \(suf(P_i)\), teda či \(A_{i+1} = B_{|suf(P_i)|+1}\). Ak áno, našli sme prefix \(B\) končiaci v \(i+1\) a \(P_{i+1}\) je \(suf(P_i)\) s pridaným znakom \(A_{i+1}\) na koniec.
• Ďalej, ak sme nenašli prefix \(B\) končiaci na \(i+1\), skúsime kratší sufix \(P\) a overíme \(A_{i+1} = B_{|suf(suf(P_i))|+1}\)
• …
• Na konci overíme \(A_{i+1} = B_{1}\) a dostaneme buď \(P_{i+1} = \emptyset\) alebo \(P_{i+1} = B_1\).

Program skončí (nájde \(B\) v \(A\)), ak \(P_i = B\), teda ak najdlhší prefix \(B\) končiaci na pozícii \(i\) je samotné \(B\).

Aká je časová zložitosť takéhoto programu? Vždy, keď Zdeno uvidí nový znak \(A_{i+1}\), overíme, či vieme aktuálnemu prefixu \(P_i = B_1 B_2 \ldots B_{|P_i|}\) (\(B\) označuje úsek, ktorého dopozeranie overujeme) pridať na koniec tento znak, teda či \(B_1 B_2 \ldots B_{|P_i|} A_{i+1}\) je prefix \(B\). Stačí nám teda len overiť, či \(A_{i+1} = B_{|P_i|+1}\). Ak nie, tak to skúsime pre prefix dĺžky \(|suf(P_i)|\). Overenie každého kratšieho prefixu trvá konštantne dlho – porovnáme 2 znaky. Pozícia začiatku prefixu \(B\), ktorý končí na pozícii \(i+1\), sa navyše vždy len zvyšuje. Z toho vyplýva, že celkovo spravíme týmto spôsobom najviac \(O(|A|)\) operácií. Ak teda máme čiernu krabičku, ktorá nám konštantne rýchlo odpovedá hodnoty \(suf(B_1 B_2 \dots B_n)\) pre každé \(n \in \lbrace 0,1,2,\ldots,|B|\rbrace\), tak časová zložitosť pre nájdenie \(B\) v \(A\) bude \(O(|A|)\).

Posledná vec, ktorú potrebujeme vyriešiť je, ako spočítame hodnoty \(suf(B_1 B_2 \dots B_n)\) – najdlhší sufix \(B_1 B_2 \dots B_n\), ktorý je prefixom \(B\). Môžeme si uvedomiť, že každý prefix \(B\) je jednoznačne určený jeho dĺžkou. Stačí nám teda pre prefix dĺžky \(n\) spočítať dĺžku jeho najdlhšieho vlastného sufixu, čo označíme \(suf(n)\).

Všimnime si, čo sme robili v horeuvedenom algoritme. Keď sme chceli zistiť najdlhší sufix slova \(B_1 B_2 \ldots B_n c\), tak nám stačilo skúšať za prefixy slova \(B_1 B_2 \ldots B_n\) pridať \(c\). To funguje aj v prípade, že \(c = B_{n+1}\). \(suf\) potom vieme spočítať dynamickým programovaním.

Na začiatku nastavíme \(suf(0)\), následne, ak poznáme \(suf(0),suf(1),\ldots,suf(n)\), tak na spočítanie \(suf(n+1)\) robíme nasledovné: vyskúšame za prefix určený \(suf(n)\) pridať \(c\), ak to nevyjde, tak za \(suf(suf(n))\), ak ani to nevyjde, tak za \(suf(suf(suf(n)))\), a tak ďalej \(\ldots\) Až kým sa nám podarí pridať \(c\), alebo nepodarí – vtedy nastavíme \(suf(n+1) = 0\). Časová zložitosť je rovnaká, ako vyššie uvedenej časti algoritmu (ale už nepotrebujeme čiernu krabičku, keďže že si tie hodnoty \(suf\) po spočítaní pamätáme), lebo sme v podstate ten istý algoritmus spustili na vstupe \(B\). Teda časová zložitosť predpočítania dĺžok prefixov bude \(O(|B|)\).

Dokopy je časová zložitosť prinajhoršom \(O(|A|+|B|)\) – presnejšie \(O(d + |B|)\) (\(d\) je vzdialenosť prejdená vlakom).

Návrat k pôvodnému problému

Pôvodný problém teda vieme riešiť nasledovne: pomocou KMP vieme vytvoriť funkciu, ktorá na vstupe dostane reťazec \(A\) reprezentujúci cestu, reťazec \(B\) reprezentujúci úsek, ktorého dopozeranie Zdeno overuje, a pozíciu vlaku na nej (prvý znak, ktorý Zdeno zatiaľ nevidel). Tá nám vráti pozíciu, na ktorej Zdeno prvýkrát dopozerá \(B\) (resp. nám povie, že taká pozícia neexistuje nejakou nezmyselnou hodnotu, napríklad \(-1\)). Označíme si \(A\) reťazec reprezentujúci cestu z Bratislavy do Košíc, a \(A'\) cestu opačným smerom (zrkadlovo obrátený reťazec). \(p, p'\) označíme aktuálne pozície vlakov. Postupne načítavame úseky \(B\) a zisťujeme, kde Zdeno dopozerá \(B\) na úseku \(A_p A_{p+1} \dots A_{|A|}\), čo zistíme volaním funkcie \(dopozeraj(A, B, p)\) a túto pozíciu zapíšeme do \(p\), podobne \(dopozeraj(A', B, p')\) zapíšeme do \(p'\).

Nakoniec overíme, či mohol Zdeno cestovať prvým smerom (či \(p \neq -1\)), a druhým smerom (či \(p' \neq -1\)), a podľa toho vypíšeme odpoveď.

Časová zložitosť je \(O((d_1 + |B_1|) + (d_2 + |B_2|) + \ldots + (d_b + |B_b|))\), kde \(d_i\) je vzdialenosť prejdená vlakom, kým Zdeno nedopozerá úsek \(B_i\). To je rovné \(O((d_1 + \ldots + d_b) + (|B_1| + \ldots + |B_b|)) = O(|A| + (|B_1| + \ldots + |B_b|))\), teda je lineárna od veľkosti vstupu.

Pamäťová zložitosť je \(O(A + max(|B_1|,|B_2|,\ldots,|B_b|))\) – nemusíme si pamätať všetky \(B_1,\ldots,B_b\) naraz, stačí ich načítavať postupne (po každom načítaní zistíme nové \(p,p'\) – pozície vlakov, a následne reťazec môžeme zahodiť, lebo ho už ďalej nepotrebujeme).

#include <bits/stdc++.h>
using namespace std;

int dopozeraj(const string& A, int poz, const string& B) {
    if (poz == -1)
        return -1;

    int suf[B.size()+1];
    suf[0] = -1;
    for (int i=1; i<=B.size(); i++) { // dlzka prefixu, pre ktory hladame jeho najdlhsi dobry sufix
        int kandidat = suf[i-1];      // dlzka kandidata -- potom posledny znak kandidata je B[kandidat - 1]
                                      // (pricom B[-1] signalizuje ziaden znak), a nasledujuci znak je B[(kandidat-1)+1]
        while (kandidat!=-1 && B[(kandidat-1)+1]!=B[i-1]) {
            kandidat = suf[kandidat];
        }
        suf[i] = kandidat+1;
    }

    // dlzka najdlhsieho prefixu konciaceho na danej pozicii
    int najpref=0; 
    while (poz!=(int)A.size() && najpref!=B.size()) {
        while (najpref!=-1 && B[(najpref-1)+1]!=A[poz]) {
            najpref= suf[najpref];
        }
        najpref++;
        poz++;
    }
    if (najpref!=B.size()) {
        return -1;
    }
    return poz;
}

int main () {
    string A1; // z Bratislavy do Kosic
    cin >> A1;
    string A2 = A1; // z Kosic do Bratislavy
    reverse(A2.begin(),A2.end());

    int n;
    cin >> n;
    int p1=0, p2=0;
    for (; n>0; n--) {
        string B;
        cin >> B;
        p1 = dopozeraj(A1,p1,B);
        p2 = dopozeraj(A2,p2,B);
    }

    bool moze1 = (p1 != -1);
    bool moze2 = (p2 != -1);
    if (moze1 && moze2) {
        cout << "neviem\n";
    }
    if (moze1 && !moze2) {
        cout << "z Bratislavy do Kosic\n";
    }
    if (!moze1 && moze2) {
        cout << "z Kosic do Bratislavy\n";
    }
    if (!moze1 && !moze2) {
        cout << "zabludil\n";
    }
    return 0;
}