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.
Fm,n := délka nejdelšího společného podřetězce s1...m a t1...m.
Fm+1,n+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 nějaké jiné přednášky.