Given: Strings X,Y ,
Table[0..x,0..y]
For i=1 to x do
Table[i,0]=i
For j=1 to y do
Table[0,j]=i
i=1, j=1
While i<=x and j<=y
If X[x]=Y[y] Then
//
matches – no underscores
Table[x,y]=Table[x-1,y-1]
Else
Table[x,y]=min(Table[x-1,y],Table[x,y-1])+1
End If
i=i+1
If i>x Then
i=1
j=j+1
End If