1 Forwards[x,y] is 2  3 1. n = length(x); m = length(y) 4 2. Edit[Prefix[0,0]] = 0; 5 3. For all i from 1 to n: 6        Edit[Prefix[x,i],Prefix[y,0]] = Edit[Prefix[x,i-1],Prefix[y,0]] + Del(x_i) 7 4. For all j from 1 to m: 8        A.  Edit[Prefix[x,0],Prefix[y,j]] = Edit[Prefix[x,0],Prefix[y,j-1]] + Ins(y_j) 9        B.  For all i from 1 to n, execute the following steps:10                i.  Edit[Prefix[x,i],Prefix[y,j]] = 11                      min{Edit[Prefix[x,i-1],Prefix[y,j]] + Del(x_i),12                          Edit[Prefix[x,i-1],Prefix[y,j-1]] + Sub(x_i,y_j),13                          Edit[Prefix[x,i],Prefix[y,j-1]] + Ins(y_j)}14                ii.  Erase Edit[Prefix[x,i-1],Prefix[y,j-1]]15        C.  Erase Edit[Prefix[x,i-1],Prefix[y,j]]16 5. RETURN Edit[x] %% an array of length m+1

 1 Backwards[x,y] is 2  3 1. n = length(x); m = length(y) 4 2. For all i from 1 to n: 5         Edit[Suffix[x,i],Suffix[y,0]] = 0 6 3. For all j from 1 to m: 7       A.  Edit[Suffix[x,0],Suffix[y,j]] = Edit[Suffix[x,n],Suffix[y,j-1]] + Ins(y_{m-j+1}) 8       B.  For all i from 1 to n: 9                 i.  Edit[Suffix[x,i],Suffix[y,j]] = 10                      min{Edit[Suffix[x,i-1],Suffix[y,j]] + Del(x_{n-i-1}),11                          Edit[Suffix[x,i-1],Suffix[y,j-1]] + Sub(x_{n-i-1},y_{m-j+1}),12                          Edit[Suffix[x,i],Suffix[y,j-1]] + Ins(y_{m-j+1})}13                ii.  Erase Edit[Suffix[x,i-1],Suffix[y,j-1]]14       C.  Erase Edit[Suffix[x,i-1],Suffix[y,j]]15 4. RETURN Edit[x] %% an array of length m+1

 1 Hirschberg(x,y) is 2  3 1. n = length(x); m = length(y) 4 2. If n <= 1 or m <= 1: 5        OUTPUT Alignment(x,y) using Needleman-Wunsch. 6     Else: 7       A.  mid = floor(n/2) 8       B.  x_left = Prefix[x,mid] 9       C.  x_right = Suffix[x,n-mid]10       D.  Edit[x_left] = Forwards(x_left,y)  %% an array of length m+111       E.  Edit[x_right] = Backwards(x_right,y) %% an array of length m+112       F.  cut = ArgMin{Edit[x_left,Prefix[y,j]] + Edit[x_right,Suffix[y,m-j]]}  %% j ranges from 1 to m-113       G.  Hirschberg(x_left,Prefix[y,cut])14       H.  Hirschberg(x_right,Suffix[y,m-cut])