# Zkouška 18. 6. 2012

<{ForumPost(poster="mjk", timestamp=2012-06-19 16:11:35)}>
Dostali jsme úlohu s písmenky, která tu na fóru už je ([28.6.2010](https://wiki.matfyz.cz/NPRG031/Zkouska%20-%2028.6.2010)), ale připadala mi nejasně napsaná a tak jsem si ji doma nepromyslel. Zkusím ji napsat ještě jednou, třeba to někomu ušetří hodinu nervů na písemce :-)  
  
**Zadání:**  
Na vstupu dostaneme slovo *S* dlouhé nejvýše 100 znaků. Dále pak nejvýše 100 přepisovacích pravidel ve tvaru *a*->*b* nebo *a*->*bc*, kde *a*, *b*, *c* jsou písmena z anglické abecedy {a..z}.  
Na výstup máme napsat všechna písmena, ze kterých jde postupným uplatňováním přepisovacích pravidel vytvořit slovo *S*. Můžeme přepsat kterýkoli znak chceme, pravidlo se nepoužije na celé současné slovo najednou.  
Např:  
Mějme vytvořené slovo "slovo" a přepisovací pravidla s->o, v->ni, o->ce. Můžeme vytvořit třeba slova "slonice", "olovo", "slonio", "celonice".  
  
Paměti máme k dispozici 400 kB a mělo by to seběhnout v rozumném čase.  
  
**Ukázkový vstup**  
abacb  
a->b  
a->c  
a->ab  
c->ac  
c->b (přidali, když zjistili, že jen s prvními čtyřmi to nedává ukázkový výstup)  
  
**Ukázkový výstup**  
a c  
  
(Např: a -> c -> ac -> abc -> abac -> abaac -> ababc -> abacc -> abacb)  
  
**Řešení**  
Dynamické programování.  
Nejprve si vygenerujeme všechny náhrady *a*->*bc*, které můžeme získat složením náhrad zadaných na vstupu. Do trojrozměrného pole *P* 26*26*26 booleanů si pak na pozici (*a*, *b*) uložíme množinu všech písmen, která mohou být skládáním pravidel změněna na *ab*.  
  
Označme *n* délku slova *S*. Vytvoříme si trojrozměrné pole *n***n**26 booleanů, kde na pozici (*i*,*j*) je množina písmen, ze kterých se dá vygenerovat úsek slova *S* o délce *i* a začínající na pozici *j*. (Na *i*-tém řádku využijeme jen prvních (*n* - *i* +1) políček, další úseky už by přečuhovaly.)  
První řádek vyplníme snadno.  Na *j*-tém políčku jsou v něm písmena, ze kterých se dá změnami typu *a*->*b* vytvořit *j*-té písmeno slova *S* a také toto písmeno (pro případ, že by slovo *S* mělo délku 1 (nebo to můžeme ošetřit nějak jinak)).   
Úseky na (*i*+1)-ním řádku (délky větší než 1) určitě vznikly ze dvou písmen (a ty dvě z jednoho), z prvního první část úseku a z druhého druhá. Předěl může být za prvním až předposledním znakem úseku, a tak všechny tyto pozice vyzkoušíme. Pro každou se podíváme na příslušné již spočítané podúseky, u každého máme uložená písmena, ze kterých se dá vygenerovat. Projdeme všechny dvojice (*a*,*b*) kde *a* generuje první podúsek a *b* druhý a pro každou dvojici zjistíme (z pole *P* na pozici (*a*,*b*)) všechna písmena, která ji generují. Ta přidáme do množiny generátorů právě počítaného úseku na řádku *i*.  
Nakonec budeme mít na pozici (*n*,1) výslednou množinu písmen, ze kterých se dá vygenerovat celé slovo *S*.  
  
Vejdeme se do 300 kB a časová složitost je O(n^3) (pokud považujeme počet písmen za konstantu + by bylo lepší tam započítat i počet pravidel).  
  
  
Někde jsem tu četl doporučení jít na ústní ten samý den, než si ty papíry zkoušející stačí pořádně přečíst. Podle toho, co říkali při zadávání, i podle toho, jak probíhala ústní, bych řekl, že je naopak (moc) nečtou. Protože jsem šel na ústní až následující den, měl jsem možnost si to pořádně promyslet, zjistit co mi v písemce chybí a na zkoušce to v podstatě přednést znovu. Tak se zařiďte podle sebe :-)
<{/ForumPost}>