Editační vzdálenost řetězců
Požadavky na absolvování
Otevřené: středa, 18. března 2020, 00.00
Termín: středa, 1. dubna 2020, 23.59
Editační vzdálenost mezi dvěma řetězci je definována jako nejmenší počet operací, jejichž aplikováním na první řetězec dostaneme druhý řetězec, kde povolené operace jsou:
- smazání jednoho znaku,
- vložení jednoho znaku,
- přepsání znaku na jiný.
Máme zadané dva řetězce A a B (ne nutně stejně dlouhé). Spočtěte jejich editační vzdálenost.
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: pokud vám úloha přijde podobná předchozí, vězte, že to není náhoda :-)