7. Celistvé tabule vzorové riešenie

(Ľ) DIAĽNICE..........
(P) ........NASTAVANIE
(S) ......CENA........

7
DIALNICE
DIALNICA
NASTAVANIE
NESTAVAME
NEBUDE
BUDE
CENA

1

3
A
BABA
ABAB

8

2
HAHA
HAHA

8

Ako ste si mohli všimnúť, táto úloha mala vela rôznych limitov pre jednoduché sady. Ako zvyčajne, znamená to existenicu veľa medzistupňových riešení ktoré váš mohli navnadiť ku vzoráku ;)

Poďme sa na ne postupne pozrieť:

Aspoň nejaké body

Prvý bod: Totálny Bruteforce

Na prvý bod si stačí poriadne prečítať ako počítame možnosti a pomocou štyroch forcyklov skúsime všetky možností pre ľavú, strednú, a pravú tabulu, a pozíciu strednej tabule. Následne zistíme či pasuje (napríklad obyčajným porovnávaním podreťazcov). Ak vám to stále nejde, zrejme ste sa oblbli niekde pri indexovaní ;)

Akú má toto riešenie zložitosť? Pamätová je lineárna – pamätáme si vstup. Pre výpočet časovej zložitosti, pozrime sa, čo robíme: pre každú možnú trojicu \((w_l, w_p, w_s)\) nám stačí skontrolovať \(|w_s|-1\) pozícií, pre každé overenie rovnosti podreťazcov treba porovnať \(|w_s|\) písmenok.

Takže celková zložitosť je \(O(n^2 \sum_i |w_i|^2)\), čo stačilo v prvej sade.

Tri body: trochu stringológie

Všimnime si, čo vlastne v horeuvedenom bruteforce robíme: hľadáme stringy v stringoch.

Ak ste už videli trochu stringológie, možno ste už počuli o KMP¹.

Je to spôsob akým nájsť všetky výskyty stringu \(t\) v stringu \(s\) v lineárnom (teda \(O(|s|+|t|)\)) čase. KMPčkom by sme tak mohli zrýchliť prechádzajúci bruteforce, tak že pre každú možnosť trojice tabúľ \((w_l, w_p, w_s)\) nájdeme všetky možné pozície kde možno dať strednú tabuľu v čase \(|w_l|+|w_r|+|w_l|\), teda celková časová zložitosť je \(O(\sum_i \sum_j \sum_l |w_l|+|w_r|+|w_l|) = O(n^2 \sum_i |w_i|)\). Pamäťová zložitosť je stále lineárna.

Toto riešenie vie prejsť na prvých troch sadách.

Štyri body: lepšia stringológia

Ak ste počuli o KMP, možno vás už strašili aj Aho-Corasickom². To je algoritmus založený na podobnom princiípe ako KMP, ale vie vyhľadávať veľa stringov naraz v lineárnom čase.

Ak ste sa tu zľakli, nebojte sa, existuje vzorové riešenie bez Aho-Corasicka a môžete túto sekciu preskočiť. Existuje však aj vzorové riešenie na základe Aho-Corasicka tak si tento algoritmus zbežne popíšeme aj v tejto sekcii:

Zo slov ktoré ideme v texte vyhľadávať (v našom prípapade sú to nápisy na všetkých tabuliach) si postavíme písmenkový strom: strom, kde každý vrchol reprezentuje prefix nejakého (alebo viacerých) z nápisov. Pre každý vrchol si vypočítame pointer na vrchol reprezentujúci najdlhší prefix ktorý je zároveň sufixom prefixu zodpovedajúcemu vrcholu (ale nie sám na seba). Tieto pointery si vieme vypočítať efektívne v lineárnom čase napríklad pomocou prehľadávania do šírky. Pomocou tejto štruktúry si potom vieme efektívne vypočítať (v čase lineárnom od celkovej dĺžky reťazcov a počtu výskytov) koľkokrát sa niektorý z hľadaných reťazcov vyskytoval v danom reťazci.

Takže pre každú dvojicu (ľavá tabuľa, pravá tabuľa) vieme zbehnúť Aho-Corasicka pre všetky ostatné tabule (dobrá správa je, že nám stačí konečný automat predpočítavať iba raz), a tak nájsť všetky pozície v čase \(O(\sum_i |w_i| + \sum_i\sum_j |w_i|) = O(n\sum_i |w_i|)\) plus počet odpovedí (čo sa pre prvé štyri sady ukáže ako dostatočne nízke číslo). Pamäťová zložitosť je stále linárna.

Pár detailov na záver: pri implementácii tohto riešenia si treba dávať pozor aby ste nezabudli že nie všetky výskyty sa rátajú (slová sa musia prekrývať), a že keď nájdeme výskyt, možno existuje iné slovo ktoré je sufixom dlhšieho výskytu, a navyše môže existovať rovnakých slov naviac. No, nie je to najvďačnejšie štvorbodové riešenie ;)

Stretnime sa v strede

Všimnime si, že doterajšie riešenia vždy počítali riešenia cez počítanie možností pre každú kombináciu ľavej a pravej tabule. Tých môže byť dokopy až pol milióna, takže vzorák musí robiť niečo trochu iné.

Čo keby sme išli a iterovali cez strednú tabuľu?

Spýtajme sa nasledovnú otázku: koľko je možností takých že \(w_i\) je stredná tabuľa, a jej prvých \(k\) znakov ide doľava a zvyšných \(|w_i|-k\) doprava?

Všimnime si, že možnosti pre ľavú a pravú tabuľu sú nezávislé: ak existuje \(L\) tabúľ takých že ich posledných \(k\) znakov sa zhoduje s prvými \(k\) znakmi \(w_i\), a \(R\) tabúľ takých že sa ich prvých \(|w_i|-k\) znakov zhoduje s prefixov \(w_i\) rovnakej dĺžky, potom odpoveď na horeuvedenú otázku je \(R\cdot L\).

Všimnime si, že keby sme vedeli odpovedať na každú z týchto otázok, stačí nám odpovede sčítať, a dostaneme takto výsledok. Navyše týchto otázok je dokopy \(\sum_i |w_i|-1\), čo je lineárne v dĺžke vstupu.

Takže ak by sme na ne vedeli odpovedať napríklad v priemerne konštantom čase, boli by sme vcelku spokojní (a vyriešili by sme úlohu).

Tri body: späť ku hrubej sile

Čísla \(R\) a \(L\) si vieme vypočítať hrubou silou: prejdeme si každého kandidáta na ľavú (alebo pravú) tabuľu, a porovnáme či sedia.

Pre každé porovnanie dokopy použijeme \(O(|w_i|)\) operácií, takže časová zložitosť bude \(O(\sum_i \sum_j |w_i|) = O(n\sum_i |w_i|)\), a pamäťová ostáva lineárna.

L, R môže byť veľa, nájdime všetky naraz

Problém je, že nemáme čas skúšať všetky možné pravé (alebo ľavé) reťazce. Musíme na to ísť trochu múdrejšie. Poďme sa na otázku ešte raz pozrieť pod lupou: chceme vlastne vedieť, pre každý prefix, koľko sufixov sa s ním zhoduje (a naopak). Namiesto porovnania s každým možným reťazcom, pamätajme si pre každý prefix počet slov pre ktoré je to prefix. Podobne pre sufixy (v separátnej mape / dicte).

Takto vieme každú z otázok zodpovedať v \(O(|w_i|)\) čase: pozrieme sa do mapy obsahujúcej všetky sufixy (resp. prefixy), zistíme koľkokrát sa náš prefix (resp. sufix) nachádza ako sufix (resp. prefix), a toto číslo si zapamätáme ako \(L\) (resp. \(R\)).

Takže nám dokopy bude trvať na otázky zodpovedať \(O(\sum_i |w_i|^2)\) v čase aj pamäti, čo stačí na štyri body.

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define FOB(i,n)	for(int i=n;i>=1;i--)
#define MP(x,y)	make_pair((x),(y))
#define ii pair<int, int>
#define lli long long int
#define ld long double
#define ulli unsigned long long int
#define lili pair<lli, lli>
#ifdef EBUG
#define DBG	if(1)
#else
#define DBG	if(0)
#endif
#define SIZE(x) int(x.size())
const int infinity = 2000000999 / 2;
const long long int inff = 4000000000000000999;

typedef complex<long double> point;

template<class T>
T get() {
    T a;
    cin >> a;
    return a;
}

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
    out << "[" << par.first << ";" << par.second << "]";
    return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}";
    return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T,U> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    
    out << "}"; return out;
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    FOR(i, v.size()){
        if(i) out << " ";
        out << v[i];
    }
    out << endl;
    return out;
}

bool ccw(point p, point a, point b) {
    if((conj(a - p) * (b - p)).imag() <= 0) return false;
    else return true;
}

void increase_val(string key, unordered_map<string, int> &mapa) {
    if (mapa.count(key)) mapa[key] ++;
    else mapa[key] = 1;
}

lli return_val(string key, unordered_map<string, int> &mapa) {
    if (mapa.count(key)) return mapa[key];
    else return 0;
}

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n = get<int>();
    vector<string> slova;
    FOR(i, n) slova.push_back(get<string>());
    int L = 0;
    FOR(i, n) L = max(L, SIZE(slova[i]));
    
    vector<unordered_map<string, int> > suff_by_len(L), pref_by_len(L);
    FOR(i, n) {
        int l = SIZE(slova[i]);
        FOR(j, l) {
            increase_val(slova[i].substr(l - j - 1, j + 1), suff_by_len[j]);
            increase_val(slova[i].substr(0, j + 1), pref_by_len[j]);
        }
    }
    
    DBG FOR(i, L) cerr << suff_by_len[i].size() << " " << pref_by_len[i].size() << endl;
    
    DBG cout << "Suffixes\n " << suff_by_len << "Prefixes:\n " << pref_by_len;
    
    lli cnt = 0;
    FOR(i, n) {
        int l = SIZE(slova[i]);
        for(int j = 0; j < l - 1; j ++) { // not entirely in one
            lli pf_matches = return_val(slova[i].substr(0, j + 1), suff_by_len[j]);
            if (pf_matches) {
                cnt += pf_matches * return_val(slova[i].substr(j + 1, l - j - 1), pref_by_len[l - j - 2]);
            }
        }
    }
    
    cout << cnt << endl;
    
    
    
    
}

Špeciálne prípady: AAAAAA

Ak sú všetky písmenká na ceduliach rovnaké, potom si nám v mapách stačí pamätať dĺžky (namiesto celých slov), čím vieme na otázku zrazu zodpovedať v konštantom čase, čím dostaneme riešenie na sadu 5 v lineárnom čase a pamäti.

Špeciálne prípady: Binárka

Nielen unárnu sústavu vieme zakódovať do jediného čísla: ak používame iba dva znaky a máme dostatočne malé slová (ako v sade 7), vieme si každé slovo “zakódovať” do čísla zmestiaceho sa do bežnej premennej (long long v C++). Keďže počítaču ide porovnávanie \(60\)-bitových čísel oveľa rýchlejšie ako porovnávanie \(60\)-znakových reťazcov, vieme sa tak tváriť že takto si vieme šikovne zakódovať (a porovnávať) sufixy a prefixy v lineárnom čase (a pamäti).

Vzorové riešenie: Hashujeme, alebo riskujeme nejednoznačné kódy

Nápad s binárkou vieme ďalej generalizovať: namiesto binárnej sústavy vieme vidieť nápisy ako čísla v \(26\)-kovej (alebo väčšej) sústave. Poviete si možno: počkaj Paulinka, načo je nám to dobré, veď takéto veľké čísla sa mi už tobôž nezmestia ani do long longu!

Našťastie, príde na pomoc hashovanie. Totiž ak vidíme slová ako čísla v prvočíselnej sústave (pre dostatočne veľké prvočíslo), keď ich zmodulujeme (veľkým) prvočíslom dostaneme niečo skoro náhodné³, a táto hodnota sa volá hash (a technika hashovanie). Čo nám pomôže že sú náhodné? Že je veľmi nepravdepdobné, že dve rôzne slová majú rovnaký hash, takže si dovolíme tvrdiť že keď dve slová majú rovnaký hash, sú rovnaké.

Hash slova \(c_0 c_1 \dots c_{l-1}\) vypočítame ako \(c_0 p^0 + c_1 p^1 + \dots + c_{l-1} p^{l-1} \mod P\) (kde \(c_i\) sú znaky konvertované na čísla). Všimnite si, že pomocou prefixových súčtov si vieme vypočítať hash (vynásobený nejakým \(p^i\)) akéhoľvek prefixu, alebo sufixu v konštatnom čase. Ak chceme porovnanávať hashe, ako sa zbavíme \(p^i\) navyše? Najjednoduchšie riešenie si je všetky hashe (prefixové aj sufixové) ktoré si budeme udržovať v mape “zarovnať” na nejakú veľkú mocninu, takže namiesto \(c_0 p^0 + c_1 p^1 + \dots + c_{k-1} p^{k-1}\) si zapamätáme \(c_0 p^C + c_1 p^{C+1} + \dots + c_{l-1} p^{C+l-1}\) (kde \(C\) je napríklad dĺžka najväčšieho slova). Podobne aj pre sufixy.

Zvyšok riešenia je už podobné ako horeuvedené mapové riešenia: \(L\) si spočítame spočítaním “odsadeného” hashu prefixu \(w_i\) o dĺžke \(k\), a zistíme si v mape sufixov koľko z nich má rovnaký hash, a to je naša hodnota \(L\). \(R\) počítame analogicky.

Takto dostaneme riešenie v čase aj pamäti \(O(\sum_i |w_i|)\), teda lineárnom vo veľlkosti vstupu.

Čo sa tu môže pokaziť? Pamätáte si na skoro náhodné? Problém je, že pri našom počte stringov sa môže stať (aj je to vcelku pravdepodobné), že nastane kolízia (a teda dve iné slová majú rovnaký hash). Ako sa tomu vyhnúť? Riešenie je zvýšiť počet “infomácie” ktoré o slovách máme (okrem hashu) tak aby sa nám stále dali jednoducho (lacno) porovnávať, ale znížili sme náhodu kolície. Jedna z možností je mať pole pre každú dĺžku prefixov (a sufixov), takže sa nám nestane kolízia medzi dvoma inak dĺhými reťazcami. Je (veľká) šanca že ani to nie je dosť, a riešenie je pridať druhý hash (teda buď iné prvočíslo \(P\), alebo iné provočíslo \(p\), alebo oba) a v mape si pamätať hashe dva. Prečo to by už malo stačiť? Keďže sú hashe “približne náhodné” kolícia zodpovedá tomu že dve náhodné čísla v rozsahu od \(0\) po \(P-1\) sú rovnaké, čo je približne narodeninový paradox. Ten nám hovorí, aby sme mali malú pravdepodobnosť kolízie mali by sme mať \(P\) (respektívne počet možných hashov) byť približne kvadratický od počtu rôznych stringov, takže dva \(P\) približne v oblasti bilióna by malo na milión (pod)reťazcov stačiť :)

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define lli long long int
#define lili pair<lli, lli>
#define SIZE(x) int(x.size())


void increase_val(lli k1, lli k2, lli P, unordered_map<lli, int> &mapa) {
    lli key = k1 + P * k2;
    if (mapa.count(key)) mapa[key] ++;
    else mapa[key] = 1;
}

lli return_val(lli k1, lli k2, lli P, unordered_map<lli, int> &mapa) {
    lli key = k1 + P * k2;
    if (mapa.count(key)) return mapa[key];
    else return 0;
}

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n;
    cin >> n;
    vector<string> slova(n);
    FOR(i, n) cin >> slova[i];
    int L = 0;
    FOR(i, n) L = max(L, SIZE(slova[i]));
    
    lli b1 = 131, b2 = 191;
    lli P = 1876956019;
    
    vector<vector<lili> > hashe(n, vector<lili>(1,{0, 0}));
    vector<lli> pw1(1, 1LL), pw2(1,1LL);
    FOR(i, L) pw1.push_back((pw1[i] * b1) % P);
    FOR(i, L) pw2.push_back((pw2[i] * b2) % P);
    
    FOR(i, n) {
        FOR(j, SIZE(slova[i])) {
            lli c = slova[i][j];
            hashe[i].push_back({(hashe[i][j].first + ((c * pw1[j]) % P)) % P, 
                (hashe[i][j].second + ((c * pw2[j]) % P)) % P});
        }
    }
    
    vector<unordered_map<lli, int> > suff_by_len(L), pref_by_len(L);
    FOR(i, n) {
        int l = SIZE(slova[i]);
        FOR(j, l) {
            lli hs1 = (P + hashe[i][l].first - hashe[i][l - j - 1].first) % P;
            lli hs2 = (P + hashe[i][l].second - hashe[i][l - j - 1].second) % P;
            lli offset1 = pw1[L - l + j + 1], offset2 = pw2[L - l + j + 1];
            lli sh1 = (hs1 * offset1) % P, sh2 = (hs2 * offset2) % P;
            increase_val(sh1, sh2, P, suff_by_len[j]);
            offset1 = pw1[L]; offset2 = pw2[L];
            increase_val((offset1 * hashe[i][j + 1].first) % P, 
                         (offset2 * hashe[i][j + 1].second) % P, 
                         P, pref_by_len[j]);
        }
    }
    
    lli cnt = 0;
    FOR(i, n) {
        int l = SIZE(slova[i]);
        for(int j = 0; j < l - 1; j ++) {
            lli offset1 = pw1[L], offset2 = pw2[L];
            lli pf_matches = return_val((offset1 * hashe[i][j + 1].first) % P, 
                                        (offset2 * hashe[i][j + 1].second) % P, 
                                        P, suff_by_len[j]);
            if (pf_matches) {
                offset1 = pw1[L - (j + 1)]; offset2 = pw2[L - (j + 1)];
                lli hs1 = (hashe[i][l].first - hashe[i][j + 1].first + P) % P;
                lli hs2 = (hashe[i][l].second - hashe[i][j + 1].second + P) % P;
                cnt += pf_matches * return_val((offset1 * hs1) % P, 
                                               (offset2 * hs2) % P, P, 
                                               pref_by_len[l - j - 2]);
            }
        }
    }
    
    cout << cnt << endl;
    
    
    
    
}

Alternatívny vzorák alebo Aho-Corasick sa vracia

Iné alternatívne riešenie ktoré sa nespolieha na náhodu je využiť písmenkový strom, ktorý nám vznikne pri predpočítaní Aho-Corasicka.

Spomeňme si, že otázka ktorá nás zaujíma je: pre daný sufix, koľko existuje zhodujúcich sa prefixov? (alebo naopak, rozmyslite si, ako odpoveď na túto otázku možno počítať na počítanie zhodných sufixov pre daný prefix). V Aho-Corasickovom písmenkáči si pre každý vrchol pamätáme ktorý je najdlhší nezhodný sufix, ktorý je slovu vo vrchole prefixom.

Túto informáciu vieme využiť na spočítanie, pre každý prefix, koľko slov existuje ktorým je tento prefix sufixom a to formou dynamického programovania. Vieme si pre každý vrchol zistiť ktoré vrcholy doňho majú pointer. Potom v poradí od najhlšieho po najkratšie prefixy (teda obrátené poradie od BFS), je hodnota pre vrchol počet slov ktoré v ňom končia plus súčet hodnôt vrcholov ktoré naňho majú pointer.

Keď máme toto predpočítané, ako rýchlo prejdeme cez všetky miesta v strome odpovedajúce sufixom? Tu použijeme príjemnú vlastnosť stromu: slovo ktorého sufixy sledujeme je už v strome. Takže si nájdeme kde sa končí, a potom pre každý zaujímavý sufix skĺzneme o rodiča nižšie.

Takto spočítame hodnoty \(R\), ako na \(L\)? Stačí nám nápisy obrátiť a spraviť rovnakú procedúru pre písmenkový strom sufixov (a hľadanie prefixov).

Všetko predpočítanie aj prehľadávanie vieme robiť v lineárnom čase aj pamäti a takto dostaneme ďalšie možné riešenie na plný počet bodov.

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define lli long long int
#define SIZE(x) int(x.size())

struct tria {
    int depth;
    char c;
    tria *pointer_to;
    tria *otec;
    int end_of;
    lli all_ends;
    vector<tria *> deti;
    
    tria (int d, char ch, tria *father) {
        depth = d;
        c = ch;
        otec = father;
        end_of = false;
        pointer_to = NULL;
        deti.resize(30, NULL);
        end_of = 0, all_ends = 0;
    }
    
    void add_word(string &s, int id) {
        if (id == s.size()) {
            end_of ++;
            all_ends ++;
            return;
        }
        int it = s[id] - 'A';
        if (deti[it] == NULL) deti[it] = new tria(depth + 1, s[id], this);
        deti[it] -> add_word(s, id + 1);
    }
};

void aho_corastic_pattern_prep(tria *root) {
    queue<tria *> Q;
    stack<tria *> S;
    Q.push(root);
    root -> pointer_to = root;
    while (Q.size()) {
        tria *t = Q.front();
        S.push(t);
        Q.pop();
        
        for (auto c : t -> deti) {
            if (c == NULL) continue;
            if (t == root) c -> pointer_to = root;
            else {
                tria *kde = t -> pointer_to;
                c -> pointer_to = root;
                do {
                    if (kde -> deti[c -> c - 'A'] == NULL) 
                        kde = kde -> pointer_to;
                    else {
                        c -> pointer_to = kde -> deti[c -> c - 'A'];
                        break;
                    }
                } while (kde != root);
                if (kde == root && root -> deti[c -> c - 'A'] != NULL) 
                    c -> pointer_to = root -> deti[c -> c - 'A']; 
            }
            Q.push(c);
        }
    }
    
    while (S.size()) {
        tria *t = S.top();
        S.pop();
        t -> pointer_to -> all_ends += t -> all_ends;
    }
}

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n;
    cin >> n;
    vector<string> slova(n);
    FOR(i, n) cin >> slova[i];
    
    tria *root_pf = new tria(0, '-', NULL), *root_sf = new tria(0, '-', NULL);
    FOR(i, n) {
        root_pf -> add_word(slova[i],0);
        string rev = slova[i];
        reverse(rev.begin(), rev.end());
        root_sf -> add_word(rev, 0);
    }
    aho_corastic_pattern_prep(root_pf);
    aho_corastic_pattern_prep(root_sf);
    
    lli cnt = 0;
    FOR(i, n) {
        tria *pf = root_pf, *sf = root_sf;
        pf = root_pf -> deti[slova[i][0] - 'A'];
        for (int j = slova[i].size() - 1; j >= 1; j --) {
            sf = sf -> deti[slova[i][j] - 'A'];
        }
        
        for (int j = 0; j < slova[i].size() - 1; j ++) {
            cnt += pf -> all_ends * sf -> all_ends;
            pf = pf -> deti[slova[i][j + 1] - 'A'];
            sf = sf -> otec;
        }
    }
    cout << cnt << endl;
}