Toto je stará verze stránky ÚlohaEditačníVzdálenost z 2007-04-23 21:32:55..

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

F_m,n := délka nejdelšího společného podřetězce s_1...m a t_1...m.

F_m+1,n+1 =

F_m,n, když s_m+1 = t_n+1
max(F_m,n+1, F_m+1,n), když s_m+1 ≠ t_n+1

F_0,x = F_x,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