Zadanie

David si z knižnice požičal lexikón kúziel. V lexikóne kúziel sa ukrýva jeho obľúbené zaklínadlo. Chcel nájsť, koľkokrát sa tam nachádza. Lenže! Čarodejnica pred ním zo srandy lexikón zakliala, takže sa po každom prečítaní text trochu zmení. David bol tvrdohlavý a po každej zmene lexikónu znova zisťoval, koľkokrát je tam zaklínadlo. Toto robil, až kým mu neuplynula výpožičná lehota a keďže nechcel platiť pokutu, musel lexikón vrátiť.

Úloha

Máme reťazec a podreťazec, v reťazci hľadáme počet výskytov podreťazca. Reťazec sa mení. Po každej zmene chceme znova zistiť počet výskytov podreťazca.

Formát vstupu

V prvom riadku je reťazec dlhý \(n\) (\(1 \leq n \leq 10^6\)). V druhom riadku je podreťazec dlhý \(m\) (\(1 \leq m \leq 10^4\)). Možeš predpokladať, že \(m \leq n\). V treťom riadku je číslo \(q\) (\(0 \leq q \leq 10^3\)). Nasleduje \(q\) riadkov vo formáte [\(p\)] [\(S\)], \(p\) označuje miesto v texte, kam zapísať podreťazec \(S\) (\(0 \leq p \leq n-m\)). Dĺžka podreťazca \(S\) je rovná \(m\), to znamená, že dĺžka reťazca sa celý čas nemení.

Formát výstupu

Na výstupe je \(1+q\) riadkov, jeden pre pôvodný text a jeden pre každú zmenu v reťazci. Na každom riadku je jedno číslo, počet výskytov podreťazca v reťazci.

V niektorých pomalších jazykoch (python) nemusí správne riešenia prechádzať na plný počet bodov. Body za popis táto skutočnosť neovplyvní. ## Príklady

Input:

BANANANOS
NANA
2
5 ANAS
3 XXXX

Output:

1
2
0

V pôvodnom reťazci sa podreťazec “NANA” vyskytuje raz. Potom sa reťazec zmení na “BANANANAS”, preto sa tam podreťazec vyskytuje dvakrát. Potom sa zmení na “BANXXXXAS”, kde už sa podreťazec nevyskytuje.

Input:

AAAAAAAAAAAAAAA
AAA
2
1 XXX
6 XXX

Output:

13
9
4

Input:

BALALAJKA
ALA
2
5 ALA
1 BLA

Output:

2
3
2

Input:

BLBALABLA
BL
2
1 LB
2 AL

Output:

2
2
2

Input:

BABANANASSSSSS
NANA
1
1 XXXX

Output:

1
0

Úlohou bolo hľadať počet výskytov podreťazca v reťazci, ktorý sa mení. Po každej zmene bolo treba znova zistiť počet výskytov podreťazca.

Pomalé riešenie

Prvou možnosťou je jednoduché prehľadanie reťazca, pričom pre každú pozíciu overíme, či sa na nej začína podreťazec. Overenie prebehne porovnávaním znakov podreťazca s aktuálne overovanou časťou reťazca. Pre každý znak, ktorých je \(n\), skontrolujeme prinajhoršom \(m\) znakov, teda celkovo urobíme \(O(nm)\) operácii. Časová zložitosť je teda \(O(nm)\) Po každej zmene reťazca, ktorých je \(q\), kontrolujeme znovu celý reťazec, teda časová zložitosť riešenia bude \(O(qnm)\). Pamäťová zložitosť je \(O(n+m)\), lebo okrem reťazca a podreťazca si nemusíme nič pamätať. Toto riešenie prejde prvou sadou testov.

#include <iostream>

std::string text, pattern;

int substrSearchNaive() {
    int patternsFound = 0;
    for (size_t i = 0; i < text.length(); i++) {
        bool found = true;
        for (size_t j = 0; j < pattern.length(); j++) {
            if (text[i + j] != pattern[j]) {
                found = false;
                break;
            }
        }
        patternsFound += found;
    }
    return patternsFound;
}

int replaceNaive(const size_t where, const std::string &what) {
    text.replace(where, what.length(), what);
    return substrSearchNaive();
}

int main() {
    int q;
    std::cin >> text >> pattern >> q;
    int patternCount = substrSearchNaive();
    std::cout << patternCount << "\n";
    for (int i = 0; i < q; i++) {
        int where;
        std::string what;
        std::cin >> where >> what;
        patternCount = replaceNaive(where, what);
        std::cout << patternCount << "\n";
    }
}

Trochu lepšie riešenie

Pomalé riešenie môžeme vylepšiť tak, že celý text prehľadáme len raz a po každej zmene už prehľadáme len zaujímavú časť reťazca. Zaujímavá je samotná zmenená časť a aj rovnako dlhá časť pred ňou a po nej. To je potrebné aby sme zistili, či sa úpravou textu neporušil alebo nevytvoril nový výskyt, ktorý sa nenachádal úplne celý v zmenenej časti textu. Keďže sme neprehľadali celý reťazec, musíme zistiť rozdiel počtu výskytov podreťazca v zaujímavej časti pred a po zmene, čiže zaujímavú časť musíme prehľadať dvakrát. Po úvodnom prehľadaní si zapamätáme počet výskytov v celom reťazci a ten potom zvyšujeme alebo znižujeme pomocou rozdielu získaného po každej zmene. Časová zložitosť sa tým zlepší na \(O(nm+qm^2)\). Pamäťová zložitosť sa oproti predošlému riešeniu nezmení. Toto riešenie prejde prvé dve sady testov.

#include <iostream>

std::string text, pattern;

int substrSearchNaive(size_t start=0, size_t end=-1u) {
    int patternsFound = 0;
    for (size_t i = start; i < std::min(end, text.length()); i++) {
        bool found = true;
        for (size_t j = 0; j < pattern.length(); j++) {
            if (text[i + j] != pattern[j]) {
                found = false;
                break;
            }
        }
        patternsFound += found;
    }
    return patternsFound;
}

int substrSearchNear(const int where) {
    int patternsFound = 0;
    size_t start = std::max(0, where - (int) pattern.length());
    size_t end = std::min(text.length(), where + pattern.length() * 2);
    return substrSearchNaive(start, end);
}

int replaceNaive(const size_t where, const std::string &what) {
    int previousCount = substrSearchNear(where);
    text.replace(where, what.length(), what);
    int currentCount = substrSearchNear(where);
    return currentCount - previousCount;
}

int main() {
    int q;
    std::cin >> text >> pattern >> q;
    int patternCount = substrSearchNaive();
    std::cout << patternCount << "\n";
    for (int i = 0; i < q; i++) {
        int where;
        std::string what;
        std::cin >> where >> what;
        patternCount = replaceNaive(where, what);
        std::cout << patternCount << "\n";
    }
}

Rabinov-Karpov algoritmus

Algoritmus spočíva na rolling hash funkcii. To je taká hash funkcia, ktorá vie vypočítať nový hash pomocou starého hashu v konštantnom čase. Na začiatku si vypočítame hash podreťazca a hash prvých \(m\) znakov reťazca. Tak isto ako v pomalom riešení prehľadávame reťacec po znakoch, avšak výskyt podreťazca neoverujeme pre každú pozíciu, ale len ak sa zhoduje hash práve prehľadávanej časti textu s hashom hľadaného podreťazca. Po každom znaku vieme zo starého hashu vypočítať nový v konštantnom čase. Časová zložitosť tohto riešenia je v najhoršom prípade \(O(mn+qm^2)\) čo je zložitosť predchádzajúceho riešenia, ale v očakávanom a veľmi pravdepodobnom prípade \(O(n+qm)\) čo je zložitosť optimálneho riešenia. Prvý prípad nastane, ak sa text skladá iba z podreťazca, čiže podreťazec sa vyskytuje na každej pozícii. Tomuto sa môžeme vyhnúť a algorimus urýchliť vynechaním overenia v prípade zhody hashu. Vtedy hrozí, že v prípade kolízie hashu nesprávne určíme, že sa vyskytol podreťazec. Dá sa ukázať, že kolizii je veľmi málo, navyše sa vyskytnú v iných prípadoch závisiacich od zvolenej hashovacej funkcie resp. prvočísla, ktorým modulujeme. Pre zníženie pravdepodobnosti kolízie môžeme použiť viac ako jednu hashovaciu funkciu. Pamäťová zložitosť bude \(O(n+m)\), keďže si pamätáme reťazec dĺžky \(n\) a podreťazec dĺžky \(m\). Toto riešenie prejde prvé tri sady testov a v prípade vynechania overenia prvé štyri sady testov.

#include <iostream>
#include <cmath>

// ALPHABET_SIZE is the number of characters in the input alphabet
#define ALPHABET_SIZE 256
#define PRIME_MODULUS 15285151248481

int64_t patternHash = 0;
int64_t hashSlider = 1;

int search(const std::string &pattern, const std::string &text) {
    int result = 0;
    int64_t slidingHash = 0;

    // Calculate the hash value of pattern and first
    // window of text
    for (size_t i = 0; i < pattern.length(); i++) {
        slidingHash = (ALPHABET_SIZE * slidingHash + text[i]) % PRIME_MODULUS;
    }

    // Slide the pattern over text one by one
    for (size_t i = 0; i <= text.length() - pattern.length(); i++) {

        // Check the hash values of current window of text
        // and pattern. If the hash values match then only
        // check for characters on by one
        if (patternHash == slidingHash) {
            bool found = true;
            /* Check for characters one by one */
            for (size_t j = 0; j < pattern.length(); j++) {
                if (text[i + j] != pattern[j]) {
                    found = false;
                    break;
                }
            }
            result += found;
        }

        // Calculate hash value for next window of text: Remove
        // leading digit, add trailing digit
        if (i < text.length() - pattern.length()) {
            slidingHash = (ALPHABET_SIZE * (slidingHash - text[i] * hashSlider) + text[i + pattern.length()]) % PRIME_MODULUS;

            // We might get negative value of slidingHash, converting it
            // to positive
            if (slidingHash < 0)
                slidingHash += PRIME_MODULUS;
        }
    }
    return result;
}

void calculatePatternHash(const std::string &pattern) {
    for (size_t i = 0;  i < pattern.length(); i++) {
        patternHash = (ALPHABET_SIZE * patternHash + pattern[i]) % PRIME_MODULUS;
        if (i != pattern.length() - 1) {
            hashSlider = (hashSlider * ALPHABET_SIZE) % PRIME_MODULUS;
        }
    }
}

int main() {
    std::string pattern, text;
    int numChanges;
    std::cin >> text >> pattern >> numChanges;
    calculatePatternHash(pattern);
    int patternCount = search(pattern, text);
    std::cout << patternCount << "\n";
    for (int i = 0; i < numChanges; i++) {
        int where;
        std::string what;
        std::cin >> where >> what;
        const int textOffset = std::max(0, (int) (where - what.length()));
        std::string subText = text.substr(textOffset, pattern.length() * 3);
        const int prevCount = search(pattern, subText);
        text.replace(where, what.length(), what);
        subText.replace(what.length(), what.length(), what);
        subText = text.substr(std::max(0, (int) (where - what.length())), pattern.length() * 3);
        const int currCount = search(pattern, subText);
        patternCount += currCount - prevCount;
        std::cout << patternCount << "\n";
    }
}

Vzorové riešenie

Vzorové riešenie využíva KMP algoritmus. Časová zložitosť predspracovania, čiže konštrukcie funkcie next bude \(O(m)\) a samotné prehľadanie reťazca bude trvať \(O(n)\). Po prvom prehľadaní celého reťazca už kontroluje len zaujímavé časti reťazca. Zaujímavá je samotná zmenená časť a aj rovnako dlhá časť pred ňou a po nej. To je potrebné aby sme zistili, či sa úpravou textu neporušil alebo nevytvoril nový výskyt, ktorý sa nenachádal úplne celý v zmenenej časti textu. Časová zložitosť riešenia bude \(O(n+qm)\). Pamäťová zložitosť bude \(O(n+m)\), keďže si pamätáme reťazec dĺžky \(n\) a podreťazec a automat dĺžky \(m\).

#include <iostream>
#include <cstring>
#include <vector>

std::vector<size_t> next;
std::string text, pattern;

void constructPrefix() {
    next = std::vector<size_t>(pattern.length(), 0);
    size_t state = 0; // dlzka najdlhsieho prefixosuffixu
    size_t i = 1; // prave spracovavane pole funkcie, musi zacinat od 1, lebo prvy prvok bude vzdy 0
    while (i < pattern.length()) {
        // pokym sedi znak z podretazca
        if (pattern[i] == pattern[state]) {
            next[i] = ++state;
            i++;
        }
        // vykonava sa, ak doslo k nezhode az pokym je stav > 0
        else if (state > 0) {
            state = next[state - 1];
        } else {
            next[i] = 0;
            i++;
        }
    }
}

/*
 * prehlada cast textu ohranicenu cez parametre start a end
 * vrati pocet vyskytov podretazca v prehladanej casti
 */
int kmpSearch(const size_t start, const size_t end) {
    int patternOccurences = 0;
    size_t state = 0;
    for (size_t i = start; i <= end; i++) {
        char textChar = text[i];
        // ak doslo k nezhode, vratit stav automatu na najblizsi mozny zaciatok podretazca
        while (state > 0 && textChar != pattern[state]) {
            state = next[state - 1];
        }
        // ak sedi znak s podretazcom, zvysit stav automatu
        if (textChar == pattern[state]) {
            state++;
        }
        // ak je stav rovny dlzke podretazca, nasiel sa jeho vyskyt
        if (state == pattern.length()) {
            patternOccurences++;
            state = next[state - 1];
        }
    }
    return patternOccurences;
}

/*
 * upravi retazec a vrati rozdiel poctov vyskytov podretazca v retazci pred a po uprave
 */
int updateText(const int where, const std::string &what) {
    // oznacuje poziciu prveho zaujimaveho znaku v retazci
    // prvy vyskyt, ktory ovplyvnime je ten, ktoreho posledny znak je na prvej zmenenej pozicii v texte
    size_t start = std::max(0, where - (int) pattern.length() + 1);
     // oznacuje poziciu posledneho zaujimaveho znaku v retazci
     // posledny vyskyt, ktory ovplyvnime je ten, ktoreho prvy znak je na posledej zmenenej pozicii v texte
    size_t end = std::min(text.length() - 1, where + pattern.length() * 2 - 2);
    int occurencesBeforeReplace = kmpSearch(start, end);
    text.replace(where, what.length(), what);
    int occurencesAfterReplace = kmpSearch(start, end);
    return occurencesAfterReplace - occurencesBeforeReplace;
}

int main() {
    int q;
    std::cin >> text >> pattern >> q;
    constructPrefix(); // skonstruovanie automatu pre nas podretazec, bude rovnaky pre cely priebeh
    int patternCount = kmpSearch(0, text.length()); // uvodne prehladanie celeho retazca
    std::cout << patternCount << "\n";
    for (int i = 0; i < q; i++) {
        int where;
        std::string what;
        std::cin >> where >> what;
        patternCount += updateText(where, what);
        std::cout << patternCount << "\n";
    }
}

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ť.