Zoznam úloh

2. Upratovanie

Zadanie

Možno si viete predstaviť, aké množstvo zbytočných vecí sa nazbiera za roky v T2. Miška sa rozhodla to zmeniť a vyhodiť všetky zbytočné veci. Zobrala jednu zbytočnú vec zo všetkých miest, kde sa skrývala, a vyniesla ju do koša. Kým sa však stihla vrátiť, všetky uvoľnené miesta už boli zapratané ďalšou kopou vecí. To ju neskutočne naštvalo, a tak zase zobrala nejakú vec a vyniesla ju preč. Keď sa však vrátila, našla ešte väčší neporiadok… To sa už všetci vo všetkom začali strácať. Dá sa vôbec ešte zistiť, koľko máme čoho?

Úloha

Majme reťazec zložený z malých písmen anglickej abecedy. Postupne prebehne $m$ zmien, pričom pri každej nahradíme všetky výskyty jedného konkrétneho písmena novým reťazcom písmen. Zistite počet výskytov hľadaného písmena po všetkých zmenách.

Formát vstupu

V prvom riadku vstupu sú medzerou oddelené dve čísla $n$ a $m$, kde $n$ udáva počet znakov vo vstupnom reťazci a $m$ udáva počet zmien.

V druhom riadku sa nachádza reťazec, ktorý popisuje uloženie vecí na začiatku. Nasleduje $m$ riadkov, v ktorých sa nachádza medzerou oddelené písmeno a reťazec, ktorým máme písmeno nahradiť. Všetky reťazce sa skladajú výhradne z malých písmen anglickej abecedy.

Na poslednom riadku sa nachádza písmeno, na ktoré sa pýtame.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
$1 \leq n \leq$ $100$ $1\,000$ $1\,000$ $10^5$
$1 \leq m \leq$ $20$ $100$ $1\,000$ $10^4$

Maximálna dĺžka nahrádzajúceho reťazca je v prvých troch sadách $50$ a v poslednej $1\,000$.

Formát výstupu

Vypíšte jedno číslo - počet výskytov písmena, na ktoré sa pýtame v poslednom riadku vstupu. Keďže toto číslo môže byť veľmi veľké, vypíšte ho ako zvyšok po delení $10^9+7$.

Príklad

Vstup

5 5
abcde
a aha
b tu
u je
e volne
v miesto
t

Výstup

3

Postupne nám vychádzajú reťazce: abcde –> ahabcde –> ahatucde –> ahatjecde –> ahatjvolnecdvolne –> ahatjmiestoolnecdmiestoolne. Vidíme, že na konci sa v reťazci nachádzajú tri písmená t.

Bruteforce

Najjednoduchšie je nasimulovať si jednotlivé zmeny. Pre každú zmenu nájdeme všetky výskyty daného písmena a postupne ich nahradíme daným reťazcom. Takto pre každú zmenu musíme prejsť celý reťazec v čase $O(n)$, čím dostaneme časovú zložitosť $O(n \cdot m)$. Netreba však zabúdať na to, že dĺžka reťazca sa pri nahrádzaní postupne zväčšuje. Skutočná časová zložitosť by tak rástla a program by bol pre väčšie vstupy extrémne pomalý.

Zaujímavá myšlienka

Môžeme si uvedomiť, že presný tvar výsledného reťazca nás vôbec nezaujíma. Keďže sa pýtame len na konečný počet nejakého písmena, stačí si po celý čas pamätať len to, koľkokrát sa jednotlivé písmená v reťazci momentálne nachádzajú. Ak máme napríklad zmeniť písmeno a za reťazec bcd, stačí sa pozrieť, koľko a-čok momentálne máme. Ak ich je päť, vieme, že do reťazca pribudne päť b-čok, päť c-čok a päť d-čok. Zároveň nesmieme zabudnúť, že týchto päť a-čok z reťazca zmizlo, takže ich počet musíme vynulovať (respektíve zobrať do úvahy aj to, či sa písmeno a nenachádza aj v nahrádzajúcom reťazci).

Optimálne riešenie

Keďže možných znakov v reťazci je konštantne veľa ($26$), vytvoríme si pole alebo slovník, kde si pre každé písmenko budeme pamätať jeho aktuálny počet. Na začiatku si raz prejdeme vstupný reťazec a spočítame začiatočné výskyty, čo nám zaberie čas $O(n)$. Následne spracujeme $m$ zmien. Pre každú zmenu zistíme aktuálny počet nahrádzaného písmena. Tento počet pripočítame každému písmenu, ktoré sa nachádza v nahrádzajúcom reťazci (tento reťazec musíme raz prejsť), a nakoniec aktuálny počet nahrádzaného písmena vynulujeme. Ak má nahrádzajúci reťazec maximálnu dĺžku $k$, potom spracovať jednu zmenu vieme v čase $O(k)$. Zmien je $m$, teda časová zložitosť spracovania zmien je $O(k \cdot m)$. Výsledná časová zložitosť tohto riešenia je $O(n + k \cdot m)$. Keďže si pamätáme len tabuľku výskytov pre $26$ písmen, pamäťová zložitosť je konštantná, teda $O(1)$.

n, i = map(int, input().split())
zaciatocny_str = input()
pocet = {}
abc = 'abcdefghijklmnopqrstuvwxyz'

for p in abc:
    pocet[p] = 0

for p in zaciatocny_str:
    pocet[p] += 1

for _ in range (i):
    old, new = input().split()
    k = pocet[old]

    for p in new:
        pocet[p] += k

    pocet[old] -= k

hladane = input()
print(pocet[hladane] % 1000000007)
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, ops;
    if (!(cin >> n >> ops)) return 0;

    string zaciatok;
    cin >> zaciatok;

    vector<long long> pocet(26, 0);
    long long MOD = 1000000007;

    for (char c : zaciatok) {
        pocet[c - 'a']++;
    }

    for (int i = 0; i < ops; ++i) {
        string old_str, new_str;
        cin >> old_str >> new_str;
        char old_char = old_str[0];
        long long k = pocet[old_char - 'a'];

        for (char c : new_str) {
            pocet[c - 'a'] = (pocet[c - 'a'] + k) % MOD;
        }

        pocet[old_char - 'a'] = (pocet[old_char - 'a'] - k + MOD) % MOD;
    }

    string hladane_str;
    cin >> hladane_str;
    char hladane = hladane_str[0];

    cout << pocet[hladane - 'a'] % MOD << endl;

    return 0;
}
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty