Editační vzdálenost
(
Dynamické Programování)
Minimální počet operací pro «převod» jednoho řetězce na druhý mazáním a vkládáním řetězců (symetrická úloha).
Triviální řešení: Exponenciální složitost.
Dynamicky
Fm,n := délka nejdelšího společného podřetězce s
1...m a t
1...m.
Fm+1,n+1 =
- Fm,n, když sm+1 = tn+1
- max(Fm,n+1, Fm+1,n), když sm+1 ≠ tn+1
F0,x =
Fx,0 = 0
Omáčku si domyslete podle ostatních úloh spadajících pod
Dynamické Programování.
Fígl: Ještě rekonstruovat řetězce, to taky jde...
Ještě efektivněji: O(n log n) — máme domyslet během nějaké jiné přednášky.
--tahle poznámka byla IMHO k úloze o nejdelší rostoucí podposloupnosti (TK)
- Ne, že by to bylo důležité, ale já myslím, že byla fakt k tomuhle. Pokud to někdo víte, ozvěte se a případně to opravte. Mimochodem, podle
http://en.wikipedia.org/wiki/Longest_common_substring_problem by to mělo jít snad v O(n) a ta podposloupnost (http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem) v O(n log log n). — Adam
- Mám s odstupem pocit, že to, co jsem napsal (ten předchozí řádek), nedává tak docela smysl, tak to veďte v patrnosti, protože teď nejsem schopný nad tím přemýšlet nebo to dokonce nějak opravovat. Snad časem. Omlouvám se:). — Adam
