Algoritmus - morseovka bez oddělovačů písmen

To vypadá jako takové rozvětvující se možnosti - mám řetězec, projdu písmena morseovky a najdu všechny shody od začátku, ukládám si nalezený znak + zbytek řetězce. Při další iteraci stejným způsobem projdu všechny ty zbylé řetězce, zase najdu shody, přidám nový znak k minulému a uložím zbytek řetězce. Na první pohled to vypadá jako vnořená pole, ale šlo by to asi i jako dlourozměrné pole: po první iteraci budu mít např. (do morseovky dávám nesmysly, neumím ji):

. Po další iteraci z toho vytvořím nové pole:
Ale je to jen první nápad. Dost pravděpodobně existuje efektivnější algoritmus.

Už na tom pracuju, lze najít všechny možnosti v čase O(délka vstupu + délka výstupu).
Založené je to na dynamickém programování.

http://kod.djpw.cz/ombb
Zkus zadat třeba slovo test - / . / ... / - bez oddělovačů -....-.
Pozor na to, že se zvětšující se délkou roste počet možností. Pro vstup .---..-.-....--.. (juriad) je jich již 40376 a prohlížeči to již nějakou dobu trvá.

Výpočet probíhá ve dvou fázích: posměrné a protisměrné.

Napřed se do pole ends ukládají výskyty znaků, která na dané pozici končí a navazují na nějaký předchozí text.
Zkus si zadat třeba .-.- a podívej se do pole ends; snad to pochopíš.

V druhé fázi se začne procházet pole ends od konce (odpovídá konci vstupu) a hledají se možnosti pro poslední znak, z toho se odvodí, kde musel končit předchozí znak. A pak se zavolá nad zbytkem (pro pohodlnost jsem to napsal rekurzivně, ale šlo by přepsat do cyklu).
Parciální shoda (možnost) se postupně ukládá do zásobníku result; jakmile se dojde až na začátek textu, je zásobník přetransformován na text a uložen do pole results, které je konečným výstupem.

Martin02:
Obávam sa, že to nemá praktický zmysel, pri dlhšom texte bude počet možných „vysvetlení“ textu astronomicky veľký. Navyše, okrem písmen sú v m. abecede aj číslice, rôzne špeciálne znaky ako otáznik, výkričník, úvodzovky,..

_es:
Má to význam, pokud by to skombinoval s nějakým slovníkem a ořezával nesmysly.
Morseova abeceda je bohužel hodně hustá: skoro každá jedno až čtyřznaková posloupnost kóduje nějaký znak.

juriad:
Akosi ma nenapadá, na čo by to niekomu bolo. Kde si videl (počul) morseovku bez oddeľovačov (prestávok) medzi písmenami?

„skoro každá jedno až čtyřznaková posloupnost kóduje nějaký znak.“
Ak sa zarátajú aj špeciálne znaky a číslice tak jedno až šesťznaková (cs.wikipedia.org/wiki/Morseovka#K.C3.B3d_Morseovy_abecedy). Okrem toho je na wikipedii spomenutá možnosť rozšírenia o národné znaky. Jednoducho - morseovka sa skladá z postupnosti troch znakov: bodka, čiarka a medzera a nie dvoch. Odstránenie jedného z tých troch znakov, medzery, nedáva zmysel, podobne ako odstránenie bodky či čiarky z jej zápisu.

_es:
Šifrovačky; ano i tam oddělovače také jsou, ale často nejsou zrejmé. V terénu se hodí do programu hodit deset/dvacet prvních teček a čárek a koukat, jestli z toho leze něco smysluplného.