Niestety trzeba się tu liczyć z tym, że mogą wystąpić kolizje sum kontrolnych i różne ciągi znakowe mogą być reprezentowane przez tę samą sumę kontrolną. Oprócz tego, przygotowanie sum kontrolnych może też być czasochłonne.
Zastosowanie innego algorytmu, skuteczniejszego dla tekstów mniej podobnych do siebie. Polega on na tym, że dla ciągów A oraz B tworzy się macierz o liczbie kolumn równej długości krótszego ciągu, taką że: gdzie to numer kolumny, a to numer wiersza, jeśli istnieje to ma wartość: gdzie jest to najmniejsza liczba jaka spełnia warunki oraz Istnieją dodatkowe warunki optymalizujące: dla i<k, czyli nie istnieje. Jeżeli nie istnieje oraz j nie istnieje to nie istnieje. Jeżeli nie istnieje to nie istnieje. Jeżeli to Jeżeli cały wiersz to koniec algorytmu Przykład działania: dane są ciągi POLITECHNIKA i TOALETA. Tworzymy macierz L o liczbie kolumn równej 7. T O A L E T A k=1 5 2 2 2 2 2 2 k=2 – – 12 3 3 3 3 3 – – – – 6 5 5 4 – – – – – – 12 5 – – – – – – – – oznacza komórki macierzy które są null, długość rozwiązania jest reprezentowana przez liczbę wierszy macierzy które nie są w całości null, na niebiesko zaznaczone są numery znaków ciągu POLITECHNIKA które są najdłuższym wspólnym podciągiem, w tym przypadku OLTA.
Przypisy
Kategoria:Programowanie dynamiczne