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]) {
= false;
found break;
}
}
+= found;
patternsFound }
return patternsFound;
}
int replaceNaive(const size_t where, const std::string &what) {
.replace(where, what.length(), what);
textreturn 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;
= replaceNaive(where, what);
patternCount 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]) {
= false;
found break;
}
}
+= found;
patternsFound }
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);
.replace(where, what.length(), what);
textint 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;
= replaceNaive(where, what);
patternCount 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++) {
= (ALPHABET_SIZE * slidingHash + text[i]) % PRIME_MODULUS;
slidingHash }
// 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]) {
= false;
found break;
}
}
+= found;
result }
// Calculate hash value for next window of text: Remove
// leading digit, add trailing digit
if (i < text.length() - pattern.length()) {
= (ALPHABET_SIZE * (slidingHash - text[i] * hashSlider) + text[i + pattern.length()]) % PRIME_MODULUS;
slidingHash
// We might get negative value of slidingHash, converting it
// to positive
if (slidingHash < 0)
+= PRIME_MODULUS;
slidingHash }
}
return result;
}
void calculatePatternHash(const std::string &pattern) {
for (size_t i = 0; i < pattern.length(); i++) {
= (ALPHABET_SIZE * patternHash + pattern[i]) % PRIME_MODULUS;
patternHash if (i != pattern.length() - 1) {
= (hashSlider * ALPHABET_SIZE) % PRIME_MODULUS;
hashSlider }
}
}
int main() {
std::string pattern, text;
int numChanges;
std::cin >> text >> pattern >> numChanges;
(pattern);
calculatePatternHashint 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);
.replace(where, what.length(), what);
text.replace(what.length(), what.length(), what);
subText= text.substr(std::max(0, (int) (where - what.length())), pattern.length() * 3);
subText const int currCount = search(pattern, subText);
+= currCount - prevCount;
patternCount 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() {
= std::vector<size_t>(pattern.length(), 0);
next 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]) {
[i] = ++state;
next++;
i}
// vykonava sa, ak doslo k nezhode az pokym je stav > 0
else if (state > 0) {
= next[state - 1];
state } else {
[i] = 0;
next++;
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]) {
= next[state - 1];
state }
// 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= next[state - 1];
state }
}
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);
.replace(where, what.length(), what);
textint occurencesAfterReplace = kmpSearch(start, end);
return occurencesAfterReplace - occurencesBeforeReplace;
}
int main() {
int q;
std::cin >> text >> pattern >> q;
(); // skonstruovanie automatu pre nas podretazec, bude rovnaky pre cely priebeh
constructPrefixint 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;
+= updateText(where, what);
patternCount 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ť.