NézetNyomtat

Spam (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

Spam

A spam-szűrők kicselezésére bizonyos spam-források lecserélik az üzenet karaktereit. Egy $s$ nyílt szövegre jelölje $\Phi(s)$ azt a szöveget, amit úgy kapunk, hogy minden betűt lecserélünk az alábbi ábécé szerint:
(Az ábécé szövegfájlban: spam.txt.)
Így minden $s$ nyílt szöveghez egyértelműen megadtunk egy $\Phi(s)$ kódolt szöveget. Visszafelé nem egyértelmű a hozzárendelés, lehetséges, hogy egy $\Phi(s)$ kód több különböző $s$ szövegből keletkezhetett.
Például a 'BU' szöveg kódja '|3|_|'. Ez 6 különböző szöveghez tartozhat: 'BU', 'IEU', 'BIJ', 'IEIJ', 'BLI', és 'IELI'.

Feladat

Írj programot, ami egy $s$ nyílt szövegre megmondja, hogy hány különböző nyílt szöveg létezik, aminek kódja $\Phi(s)$.

Bemenet

A bemenet minden sora egy legfeljebb 100 nagybetűs karakterből álló teszteset. A bemenet végét az "end" sor jelzi.

Kimenet

Minden kérdéshez adjuk meg a lehetséges különböző nyílt szövegek darabszámát. (Tudjuk, hogy a darabszám legfeljebb 1000000000.)

Példa

spam.inspam.out
BU UJ THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOGS end 6 5 144

Tesztadatok