Nejdelší společný podřetězec
Abschlussbedingungen
Opened: Mittwoch, 18. März 2020, 00:00
Due: Mittwoch, 1. April 2020, 23:59
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).