Zadanie
V tejto úlohe sa dozviete ako prebieha dvorenie u robotov.
Každý robot má vo svojej pamäti uložené posledné udalosti, ktoré sa v jeho/jej okolí odohrali. Každá udalosť má nejakú tému. Pre jednoduchosť si budeme pamäť každého robota predstavovať ako reťazec malých písmen anglickej abecedy. Každé písmeno označuje nejakú tému. Napr. “abca
” je pamäť obsahujúca 4 rôzne udalosti, pričom prvá a posledná udalosť majú tú istú tému.
Proces dvorenia je vo svojej podstate veľmi jednoduchý. Každý robot si vyberie nejaký neprázdny súvislý úsek svojej pamäte a prerozpráva ho druhému robotovi. Dvorenie prebehlo úspešne práve vtedy, ak v úsekoch, ktoré si prerozprávali, nájdu nejakú spoločnú tému. Napríklad ak jeden robot povie “bca
” a druhý “efccg
”, tak dvorenie bolo úspešné, lebo obaja spomenuli tému c
.
Android Helboj má veľký úspech u fembotiek. Fembotky za ním samé chodia a ako prvé mu hovoria svoje zážitky. No a Helboj to už má potom ľahké – stačí, aby si vybral nejaký úsek svojich spomienok, ktorý má s tými od fembotky nejakú spoločnú tému, a má vyhraté.
Úloha
Na vstupe dostanete dva reťazce. Prvý predstavuje postupnosť \(f\) spomienok, ktorú nejaká fembotka povedala Helbojovi. Druhý predstavuje postupnosť \(h\) spomienok, ktorá tvorí celú Helbojovu pamäť.
Helboj má presne \(h(h+1)/2\) možností, ktorý úsek spomienok prerozprávať fembotke. (Dve možnosti považujeme za rôzne, ak sa líšia indexom začiatku alebo konca, a to aj vtedy, ak im zodpovedajú rovnaké postupnosti znakov – ide síce o rovnakú tému, ale rôzne výskyty toho istého znaku predstavujú rôzne udalosti.) Váš program by mal vypočítať, koľko spomedzi týchto možností povedie k úspešnému dvoreniu.
Vstup
Prvý riadok vstupu obsahuje prirodzené čísla \(f\) a \(h\) (\(1 \leq f, h \leq 100\,000\)).
Druhý riadok obsahuje \(f\) malých písmen anglickej abecedy – úsek pamäte prerozprávaný fembotkou.
Tretí riadok obsahuje \(h\) malých písmen anglickej abecedy – celú pamäť Helboja.
Výstup
Vypíšte jeden riadok a v ňom jedno číslo – počet takých podreťazcov Helbojovej pamäte, že zdieľajú niektorú tému s fembotkiným reťazcom pamäte.
Príklady
Input:
2 2
aa
ba
Output:
2
Helboj môže povedať jeden z reťazcov “b
”, “a
” a “ba
”. Ak by ale povedal len “b
”, nenašli by s fembotkou spoločnú tému. Musí si teda vybrať jednu zo zvyšných dvoch možností.
Input:
3 6
bdb
acaabd
Output:
11
V tomto prípade vyhovujú všetky podreťazce Helbojovej pamäte, ktoré končia piatym alebo šiestym znakom.
Input:
1 10
a
aaaaaaaaaa
Output:
55
Tu si všimnite, že odpoveď je 55 a nie 10.
Najjednoduchšie riešenie, priamočiaro “hrubou silou” vyzerá nasledovne: Označme si reťazce fembotky a Helboja \(F\) a \(H\). Vyskúšame všetky možné podreťazce \(H\) – postupným výberom začiatkov a koncov. Každý podreťazec po znakoch skontrolujeme, či sa také písmenko nenachádza aj v \(F\) – prejdením celého \(F\). Ak tam bola aspoň jedna spoločná téma-písmenko, podreťazec zarátame. Časová zložitosť tohoto prístupu je \(O(h^3 \cdot f)\) – máme \(h(h+1)/2\) podreťazcov po najviac \(h\) písmen, z ktorých každý skontrolujeme za najviac \(f\) krokov.
#include <iostream>
#include <string>
using namespace std;
int main() {
int f, h;
string F, H;
cin >> f >> h;
cin >> F >> H;
long long pocet = 0;
for (int i = 0; i < h; i++) {
for (int j = i; j < h; j++) {
for (int k = i; k <= j; k++) {
bool spolocna = false;
for (int l = 0; l < f; l++) if (H[k] == F[l]) { spolocna = true; break; }
if (spolocna) { pocet++; break; }
}
}
}
cout << pocet << '\n';
return 0;
}
Všimnime si, že netreba stále prechádzať celý reťazec \(F\) – namiesto toho vieme prejsť \(F\) na začiatku raz, pre každé písmenko si zapamätať, či je v ňom a následne to rýchlo kontrolovať pri prechádzaní. Dostaneme čas \(O(f+h^3)\).
#include <iostream>
#include <string>
using namespace std;
string F, H;
bool je_v_F[32]; // tabulka pre pismenka, v globalnych je default vsade 0/false
int main() {
int f, h;
cin >> f >> h;
cin >> F >> H;
for (int i = 0; i < f; i++) je_v_F[F[i]-'a'] = true;
long long pocet = 0;
for (int i = 0; i < h; i++)
for (int j = i; j < h; j++)
for (int k = i; k <= j; k++)
if (je_v_F[H[k]-'a']) { pocet++; break; }
cout << pocet << '\n';
return 0;
}
Ďalej sa zamyslime, čo sa stane, keď v \(H\) pre daný začiatok úseku nájdeme koniec taký, že tento úsek už obsahuje spoločnú tému s \(F\). Tento koniec môžeme ľubovoľne posúvať ďalej a stále budeme mať aspoň jednu túto istú spoločnú tému. Ako nám to pomôže? Pre každý možný začiatok nájdeme najbližšie písmenko, ktoré sa vyskytuje aj v \(F\). Ak žiadne nenájdeme, tak zjavne nemáme podreťazec so spoločnou témou nikde ďalej. Nech začiatok je na pozícií \(i\) a najbližšie spoločné písmenko na \(j>=i\). Všetkých podreťazcov začínajúcich v \(i\) obsahujúcich \(j\) je \(h-j\) (ak indexujeme od \(0\) po \(h-1\)). Takže tento príslušný počet zarátame a pohneme sa na ďalší začiatok. Začiatkov je \(h\) a pre každý prejdeme najviac \(h\) písmen, čo nám dáva časovú zložitosť \(O(f+h^2)\).
#include <iostream>
#include <string>
using namespace std;
string F, H;
bool je_v_F[32];
int main() {
int f, h;
cin >> f >> h;
cin >> F >> H;
for (int i = 0; i < f; i++) je_v_F[F[i]-'a'] = true;
long long pocet = 0;
for (int i = 0; i < h; i++){
int prva_spol;
for (prva_spol = i; prva_spol < h; prva_spol++) {
if (je_v_F[H[prva_spol]-'a']) break;
}
pocet += h-prva_spol;
}
cout << pocet << '\n';
return 0;
}
Nakoniec sa pozrime, čo sa deje pri hýbaní sa na ďalší začiatok úseku. Kde mohla byť predošlá najbližšia spoločná téma? Ak bola hneď na predošlom začiatku, tak je už za nami a musíme nájsť novú. Inak je stále najbližšia tá istá. Budeme mať premennú pre pozíciu najbližšej spoločnej témy a keď sa už začiatok ocitne za ňou, budeme ju zvyšovať, kým nenájdeme dalšiu spoločnú tému alebo koniec. Túto premennú zvýšime celkovo iba \(h\)-krát a každému začiatku vieme povedať, koľko príslušných podreťazcov z neho zarátame. Dostávame rýchle vzorové riešenie v \(O(f+h)\).
#include <iostream>
#include <string>
using namespace std;
string F, H;
bool je_v_F[32];
int main() {
int f, h;
cin >> f >> h;
cin >> F >> H;
for (int i = 0; i < f; i++) je_v_F[F[i]-'a'] = true;
long long pocet = 0;
int ns = -1; // najblizsia spolocna tema (pozicia)
for (int i = 0; i < h; i++){
if (ns < i) {
for (ns = i; ns < h; ns++) if (je_v_F[int(H[ns]-'a')]) break;
}
pocet += h-ns;
}
cout << pocet << '\n';
return 0;
}
Treba si dať pozor na veľkosť odpovede – môže presiahnuť rozsah 32-bitovej premennej.
Všimnite si, ako sme z jednoduchšieho riešenia zrýchľovali. Vždy vyhodíme niečo, čo zbytočne prechádzame. Takto vieme často nájsť použiteľné riešenia. Pamäťová zložitosť bola vo všetkých prípadoch \(O(f+h)\), nakoľko sme si pamätali iba načítané reťazce a konštantne veľa pomocnej pamä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ť.