Zadanie

Janko sa začal učiť pracovať s Unixovým terminálom. Ako prvý sa naučil príkaz echo s veľmi príznačným menom, ktorý ako ozvena vypíše svoje parametre na štandardný výstup.

Potom však došiel k príkazom, ktoré začali mať príliš krátke a nezrozumiteľné mená. Začínalo to úplne nebadane, príkazmi cp, mv a rm na kopírovanie, presúvanie a mazanie súborov, ktorých mená vznikli jednoducho z CoPy, MoVe a ReMove. Neskôr sa to začalo zhoršovať. Janko sa dozvedel napríklad o príkazoch chmod (change mode), tar (tape archiver), tr (transform) či chgrp (change group). Janko si príkazy nedokázal zapamätať a v skriptoch, ktoré napísal, sa už chvíľu nato nedokázal vyznať. Ale malo to aj svoje výhody: menej búchania do klávesnice, menej prenesených mobilných dát1 , …, a tu to aj skončilo.

Kto si má všetky tie skratky pamätať, pomyslel si Janko a začal sa radšej učiť programovať v jazyku C. Vôbec si však nepomohol, práve naopak. Tu mená funkcií boli nielen prikrátke, ale priam až kryptické. Napríklad strrchr. Po dlhých minútach zamyslenia zistil, že to str znamená string, r znamená reverse a chr znamená character a funkcia teda hľadá výskyt znaku v reťazci odzadu.

Keďže ho však premýšľanie začalo bolieť, rozhodol sa už druhýkrát zmeniť predmet svojho záujmu. Vybral si jazyk SNOBOL. Ale toto už Jankovi nedalo. Prečo práve SNOBOL? Ako k tomu došli? Vraj StriNg Oriented symBOlic Language. To nijak nedáva zmysel.

Napokon došiel k tomu, že vo všeobecnosti skratka vzniká tak, že len jednoducho vyberieme niektoré znaky názvu, pričom zachováme ich poradie a zapíšeme ich za seba. Z každého slova musíme vybrať aspoň jedno písmeno. A žiadne ďalšie pravidlá zrejme neplatia.

Janko by chcel vedieť overovať, či je daná skratka platná. Ale rozmýšľanie ho už po lúštení strrchr a SNOBOLu veľmi bolí, rád by to teda nechal na vás.

Úloha

Vašou úlohou je spočítať počet možností, ako mohla vzniknúť skratka \(S\) z názvu \(T\).

Aby skratka \(S\) mohla vzniknúť z textu \(T\), musí platiť, že písmenám v \(S\) vieme priradiť písmená v \(T\), pričom musíme zachovať poradie (teda ak priradíme písmenko z \(S\) nejakému písmenku z \(T\), ďalšiemu môžeme priradiť len nejaké napravo v \(T\)) a z každého slova \(T\) musíme použiť aspoň jedno písmeno.

Keďže počet možností je v niektorých prípadoch naozaj veľký, vypíšte len jeho zvyšok po delení \(10^9+7\).

Formát vstupu

Na prvom riadku sa nachádza číslo \(w\) – počet slov textu, z ktorého má byť utvorená skratka.

Na druhom riadku sa nachádza skratka - reťazec \(S\) a na treťom riadku sa nachádza text \(T\), ktorého skratka to má byť. Oba reťazce na vstupe pozostávajú len z malých písmen anglickej abecedy a medzier. Jednotlivé slová \(T\) sú oddelené práve jednou medzerou (medzier je teda \(w-1\)). Skratka žiadne medzery neobsahuje.

Formát výstupu

Vypíšte jedno číslo – počet možností, ako možno priradiť písmenám skratky \(S\) písmená textu \(T\) tak, aby tvorili platnú skratku, modulo \(10^9+7\). Ak to nie je možné, vypíšte \(0\).

Hodnotenie

Nech \(M\) je dĺžka skratky a \(N\) dĺžka textu. Sú \(4\) sady vstupov. V jednotlivých sadách platia nasledovné obmedzenia:

  1. \(M \leq 5\), \(N \leq 12\)
  2. \(M \leq 12\), \(N \leq 50\)
  3. \(M \leq 120\), \(N \leq 200\)
  4. \(M \leq 200\), \(N \leq 10000\)

Príklady

Input:

2
tar
tape archiver

Output:

4

Možnosti sú TApe aRchiver, TApe archiveR, Tape ARchiver a Tape ArchiveR.

Input:

4
snobol
string oriented symbolic language

Output:

1

Input:

3
strrchr
string reverse char

Output:

3

Input:

4
radar
radio detection and ranging

Output:

1

Jediná možnosť je RAdio Detection And Ranging. RADio detection And Ranging nie je platná možnosť, pretože zo slova detection sme nepoužili žiadne písmeno.

Input:

4
acm
academy of computer makers

Output:

0

Skratka je jednak prikrátka, a jednak neobsahuje žiadne z písmen slova of.

  1. Znižovanie množstva prenesených dát je naozaj dôvodom, prečo majú príkazy tak veľmi skrátené názvy. Kedysi, v časoch terminálov a telefónnych liniek, to naozaj malo význam.↩︎

Zabudnime zatiaľ na obmedzujúcu podmienku v zadaní, že z každého slova musíme do skratky vybrať aspoň jedno písmeno. Keďže medzery sa v skratke nenachádzajú, bez tohto obmedzenia sa nás úloha pýta, koľkými spôsobmi možno dostať skratku – reťazec \(S\) ako podreťazec reťazca \(T\). Táto úloha sa dá riešiť jednoducho dynamickým programovaním.

Dynamické programovanie označuje techniku, kedy si problém vieme rozdeliť na menšie, výsledky pre menšie problémy si zapamätať a potom ich rovno používať, nepočítať ich znova. Naše podproblémy budú zodpovedať tú istú otázku, ale len pre menšie prefixy \(S\) a \(T\). Konkrétne: označíme si \(dp[i][j]\) počet spôsobov, ako vybrať z prvých \(i\) znakov \(T\) podpostupnosť zhodnú s prvými \(j\) znakmi \(S\). Tieto hodnoty budeme počítať od menších hodnôt \(i\) a \(j\) k väčším.

Ako vypočítať hodnotu \(dp[i][j]\), ak poznáme hodnoty pre menšie \(i\) a \(j\) Chceme teda získať prefix \(S\) dĺžky \(j\) ako podpostupnosť prefixu \(T\) dĺžky \(i\).

Ak je \(j=0\), potom zrejme existuje práve jedna možnosť, ako vybrať prázdnu podpostupnosť z niečoho, a to práve tá, že nevyberiem žiadny znak.

Ak je \(i=0\) a \(j \neq 0\), potom nie je možné z prázdneho prefixu \(T\) neprázdnu podpostupnosť.

Ak sa \(j\)-ty znak \(S\) zhoduje s \(i\)-tym znakom \(T\) , potom tento znak mohol byť z \(T\) vybraný a ostáva nám vybrať prvých \(j-1\) znakov \(S\) z o 1 kratšieho prefixu \(T\). Už vieme, koľkými spôsobmi to ide: \(dp[i-1][j-1]\). Inou možnosťou je, že sme tento znak z \(T\) nevybrali (nejaký rovnaký sme v \(T\) vybrať museli, ale skôr). To znamená, že sa pokúšame vybrať prvých \(j\) znakov \(S\) ako podpostupnosť z o 1 kratšieho prefixu \(T\), čo ide \(dp[i-1][j]\) spôsobmi. Každá možnosť konštrukcie podpostupnosti spadá do práve jedného z týchto prípadov, a teda bude započítaná práve raz.

Ak sa \(j\)-ty znak \(S\) nezhoduje s \(i\)-tym znakom \(T\), musia všetky spôsoby, ako vyrobiť žiadaný prefix, vyzerať tak, že používajú iba prvých \(i-1\) znakov \(T\).

Vďaka pamätaniu si predchádzajúcich hodnôt \(dp\) vieme každú ďalšiu hodnotu \(dp\) spočítať v konštantnom čase, teda celková časová zložitosť je úmerná počtu dvojíc \(i\) a \(j\), teda \(O(|S| \cdot |T|)\).

Ako by sme vedeli upraviť tento algoritmus, aby počítal len možnosti, kedy z každého slova zoberieme aspoň jedno písmeno?

Parametre \(i\), \(j\) dynamického programovania vlastne zodpovedajú akýmsi stavom. Stav je napríklad, že mám prefix \(S\) dĺžky \(j\) a prefix \(T\) dĺžky \(i\). V našej pôvodnej úlohe tiež môžeme nájsť nejaké stavy. Konkrétne je stavom to, že máme prefix \(S\) dĺžky \(j\), prefix \(T\) dĺžky \(i\) a buď sme už z aktuálneho slova (z toho, ktorému patrí \(i\)-ty znak \(T\)) vybrali nejaké písmeno, alebo nie. Týmto sa stavový priestor zväčší iba dvojnásobne, takže to časovú zložitosť nepokazí.

Nech teda \(dp[i][j][N]\) značí stav, kedy máme prefix \(S\) dĺžky \(j\) a prefix \(T\) dĺžky \(i\), pričom z aktuálneho slova sme ešte nepoužili žiaden znak a \(dp[i][j][P]\) značí, že sme už nejaký znak slova použili. \(N\) a \(P\) sú len symboly pre lepšie pochopenie. V implementácii môžeme použiť hodnoty \(0\) a \(1\) alebo mať dve polia, \(dp_N\) a \(dp_P\).

Ak je \(i\)-ty znak \(T\) písmeno, do stavu \(dp[i][j][N]\) sa dá dostať jedine zo stavu \(dp[i-1][j][N]\). Ak by sme totiž použili daný znak, dostali by sme sa do stavu s \(P\). To však nenastalo, a teda máme o 1 kratší prefix.

Do stavu \(dp[i][j][P]\) sme sa mohli dostať viacerými spôsobmi: - \(i\)-ty znak \(T\) sme nevybrali, museli sme vybrať nejaký znak predtým, čiže sme prišli zo stavu \(dp[i-1][j][P]\), - \(i\)-ty znak \(T\) sme vybrali (samozrejme, len ak je zhodný s \(j\)-tym znakom \(S\)) a už predtým sme vybrali nejaký iný znak slova, teda sme prišli zo stavu \(dp[i-1][j-1][P]\), - \(i\)-ty znak \(T\) sme vybrali a bol to prvý vybraný znak slova, žiaden predošlý sme nevybrali, prišli sme zo stavu \(dp[i-1][j-1][N]\).

Ostáva poriešiť hranice medzi slovami. Tie sa jednoducho riešia vtedy, ak je aktuálny (\(i\)-ty) znak \(T\) medzera. Vtedy začína nové slovo, takže počet spôsobov, ako mať vybraný nejaký znak nového (aktuálneho) slova (\(dp[i][j][P]\)) je nula. Počet spôsobov, ako nemať vybraný znak nového slova (\(dp[i][j][N]\)) je rovný \(dp[i-1][j][P]\), teda hodnota pre o 1 kratší prefix \(T\) s použitím nejakého znaku posledného slova. Všimnime si, že nezapočítavame \(dp[i-1][j][N]\), pretože to zodpovedá situácii, kedy sme z predošlého slova nič nevybrali.

Počet možností pre skúmaný stav získame ako súčet počtov možností pre stavy, z ktorých sa do aktuálneho vieme dostať.

Odpoveďou je potom odpoveď pre celý reťazec \(S\) a celý reťazec \(T\), pričom aj z posledného slova sme museli nejaké písmeno vybrať. Je to teda hodnota \(dp[|T|][|S|][P]\).

Časová zložitosť riešenia je stále \(O(|S| \cdot |T|)\), pretože máme len dvakrát viac hodnôt ako v zjednodušenom prípade a každú hodnotu vieme vypočítať v konštantnom čase.

Pamäťová zložitosť je rovnaká, ale vieme dosiahnuť aj zložitosť \(O(|S|)\), pretože pri výpočte hodnôt \(dp[i]\) nám stačí poznať hodnoty \(dp[i-1]\), teda stačí si pamätať dva stĺpce, predošlý a aktuálny, tabuľky \(dp\).

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