| Pseudocode
(top-down) |
|
|
|
|
|
|
|
|
|
|
| Given:
Strings X,Y , Table[0..x,0..y] |
|||||||||
| BestAlignment
(x,y) |
|||||||||
| Compute Table[x-1,y] if necessary |
|||||||||
| Compute Table[x,y-1] if necessary |
|||||||||
| Compute Table[x-1,y-1] if necessary |
|||||||||
| 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 |
|||||||||