Matematické Fórum

Zdravim,

pripravuju se na zkousku a mam tu jeden z prikladu:

Mame text ulozeny v poli T[1..n] bez mezer a interpunkcnich znamenek.
"Toznamenatexttohototypu" Nasim ukolem je rozhodnout, jestli text je
"platnym textem", tj. jestli se da rozdelit tak, ze vsechny jeho casti
jsou existujici slova. To jestli dane slovo je existuje(tj. jestli
to neni nesmysl) zjistime pomoci fce dict(w). Ta vrati true, prave
kdyz slovo existuje. Volani teto fce je ve tride O(1). Navrhnete
algoritmus slozitosti O(n^2) zalozeny na principu dyn. programovani,
ktery rozhodne, zda dany text T je platnym textem.

Navrhl jsem tenhle algoritmus (omluvte prosim zjednoduseny zapis, nechtel jsem to komplikovat pro ctenare)


for size = 1 to n do
for start = 1 to n-size do
   word[start, start+size] = or(k = 0 to size-1) {word[start+k, start+size], dict(T[start..start+size])}


return word(1, n)



Ta funkce or vraci true, pokud dany retezec je slovo nebo nejake rozdeleni podle k je skupina slov.
Jinak je to snad jasny. De facto zacinam na slovech velikosti 1 a postupne zvysuju a divam se do wordu, kde jsem si ty mensi cisla napocital.


Znepokuje me jedna vec ale, je vyzadovana slozitost O(n^2), ale kdybych ten muj algoritmus vice rozepsal, hlavne tu cast or, ktera je cyklus rozdeleni, tak se dostanu mimo pozadovanou slozitost.


Nenapada nekoho, jak splnit ten pozadavek?


Dekuji.