Nejkratší společný nadřetězec

V předchozí úloze jste se potkali s hledáním nejdelšího společného podřetězce. Pojďme si zadání obrátit naruby.

Máme zadané dva řetězce A a B (ne nutně stejně dlouhé). Vymyslete, jak spočítat jejich nejkratší společný nadřetězec, tj. nejkratší řetězec takový, že v něm A i B najdeme jako podřetězec – jinými slovy z něj umíme vyškrtat nějaké znaky, abychom dostali A, a taky z něj umíme vyškrtat nějaké (nejspíš jiné) znaky, abychom dostali B.

Příklad: nejkratší společný nadřetězec (resp. jeden z možných) pro řetězce A = "kočka" a B = "počítač" je "pkočkítač".

Pokud vám to pomůže, můžete předpokládat, že abeceda má konstantní velikost, není to však potřeba.