Podróż po algorytmach tekstowych, którą odbyliśmy w poprzedniej części serii, była dla mnie naprawdę fascynująca. Kto by pomyślał, że takie proste – wydawałoby się – zagadnienie, jakim jest przetwarzanie tekstu, może być takie ciekawe? Ostatnio zainteresowałem się więc kolejnym algorytmem, który dziś weźmiemy na warsztat, a jest nim  poszukiwanie najdłuższego wspólnego podciągu albo, mówiąc prościej, wyznaczaniem różnic edycyjnych pomiędzy dwoma ciągami.

Zagadnienia poruszane w tym artykule:

• Magia;
• Odległość;
• Diagram edycj;
• Algorytm prosty;
• Przenieśmy się więc do Arizony;
• Algorytm zachłanny;
• Optymalizacja pamięciowa;
• Docelowy algorytm;
• Implementacja;
• Porównywanie tekstów;

Artykuł pochodzi z magazynu Programista nr 91 (4/2020). Jest to wydanie z przełomu czerwca i lipca 2020 r. Szczegółowy spis treści wydania nr 91: https://programistamag.pl/programista-4-2020-91/

Autorem artykułu jest Wojciech Sura. Programuje od 25 lat, z czego 10 komercyjnie; ma na koncie aplikacje desktopowe, webowe, mobilne i wbudowane - pisane w C#, C++, Javie, Delphi, PHP, Javascript i w jeszcze kilku innych językach. Obecnie pracuje w firmie WSCAD, rozwijającej oprogramowanie nowej generacji CAD dla elektrotechników.