Nejdelší společný podřetězec
Completion requirements
Opened: Wednesday, 18 March 2020, 12:00 AM
Due: Wednesday, 1 April 2020, 11:59 PM
Máme zadané dva řetězce A a B (ne nutně stejně dlouhé). Vymyslete, jak spočítat jejich nejdelší společný podřetězec, tj. nejdelší řetězec takový, že ho A i B obsahují po vyškrtání nějakých písmen (ne nutně sousedících).
Příklad: nejdelší společný řetězec řetězců A = "devastace" a B = "dekadence" je "deace".
Pokud vám to pomůže, můžete předpokládat, že abeceda má konstantní velikost, není to však potřeba.
Nápověda: vzpomeňte si na úlohu o nejnižší knihovně z minule (a její řešení "rekurzí naruby" a grafovou intuici).