Konstrukcja tego algorytmu sprawia, że czas potrzebny na rozwiązanie tego problemu wzrasta kwadratowo wraz ze zwiększaniem się porównywanych ciągów. Dlatego też warto stosować różnego rodzaju optymalizacje.
W przypadku ograniczonego dostępu pamięci i potrzebie wyznaczenia jedynie długości najdłuższego wspólnego podciągu, warto zamiast tworzenia macierzy prostokątnej o wymiarach na stworzyć jedynie dwa wektory o długości w których przechowywany będzie jedynie poprzedni i aktualny wiersz. Można także wyznaczyć NWP w czasie O(nm) i pamięci O(\min\{n,m\}), wzorując się na algorytmie Hirschberga.
W przypadku gdy porównywane są 2 teksty, których mamy pewność, że na przykład początek i koniec są takie same, możemy je pominąć w analizie.
Zwykle najwięcej czasu w tym algorytmie zabiera porównywanie. Dlatego działania w kierunku zmniejszenia ilości porównań mogą być pożądane. Poszukiwanie najdłuższego wspólnego podciągu pod względem całych wyrazów, linii lub akapitów może być szybsze w stosunku do przeszukiwania poszczególnych liter. Jednak trzeba tu uważać, bo porównywanie ciągów znakowych pod względem identyczności też nie jest zbyt szybkie. W celu przyspieszenia tych porównań można sprowadzić je do porównań sum kontrolnych tych ciągów, co powinno skrócić długość porównywanych ciągów.