5. Už nemáme čo jesť vzorové riešenie

2
tar
tape archiver

4

4
snobol
string oriented symbolic language

1

3
strrchr
string reverse char

3

4
radar
radio detection and ranging

1

4
acm
academy of computer makers

0

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\).