Algorytm ten ma złożoność obliczeniową rzędu gdzie oraz to długości ciągów i Algorytm ten tworzy tablicę dwuwymiarową C (n na m) taką, że wartość C[i][j] jest długością NWP podciągów i A więc po zakończeniu wypełniania tablicy komórka będzie zawierała wartość będąca długością NWP oryginalnych ciągów wejściowych i
Optymalne rozwiązanie podproblemów Załóżmy, że w danym kroku algorytmu chcemy obliczyć wartość komórki tj. długość NWP dla podciągów i Jeżeli i są identyczne na pozycjach odpowiednio i to należy włączyć ten wspólny znak do znalezionego wcześniej wspólnego podciągu. Wtedy:
ponieważ długością NWP ciągów i będzie długość NWP podciągów i plus jeden wspólny element z pozycji i
Jeżeli znaki i są różne, to obliczenie sprowadza się do sprawdzenia, który ze wspólnych podciągów słów i oraz i jest dłuższy, i włączenie go do tablicy wynikowej.
Zatem algorytm wypełniania tablicy można zapisać jako:
Stany początkowe Do obliczenia tablicy potrzeba jeszcze tylko tzw. stanów początkowych, tj.