# Wu Algorithm(Edit-Distance, 1990)

Main features
• three editing operations
• changing one character to another single character;
• deleting one character from the given string
• inserting a single character into the given string
• searching phase in O(n*p) time complexity
Description

The edit distance problem is to find the minimum cost of edit operations to transform one string to the other. Wu presented an algorithm for edit distance problem with with that the cost of an insertion or deletion is 1 and the cost of a replacement is 2. This algorithm performs well when the two strings are similar. the ideal of the algorithm is similar to Myers's algorithm. Wu et al. reduced the search range of diagonals from the algorithm of Myers. This algorithm determine the edit distance in O(n*p) time, where p is the number of deletions in the edit operations.

C source code
```int Wu_Alg(char *A, char *B, int m, int n)
{
int *realfp = new int[m+n+3];
int *fp, p, delta;
fp = realfp + n + 1;
memset(realfp, -1, (m+n+2)*sizeof(int));
delta = n - m;
p = -1;

while(fp[delta] != n){
p=p+1;
for(int k = -p; k <= delta-1; k++){
fp[k]=snake(A, B, m, n, k, Max(fp[k-1]+1, fp[k+1]));
}
for(int k = delta+p; k >= delta+1; k--){
fp[k] = snake(A, B, m, n, k, Max(fp[k-1]+1, fp[k+1]));
}
fp[delta] = snake(A, B, m, n, delta, Max(fp[delta-1]+1, fp[delta+1]));
}
delete [] realfp;
return delta+2*p;
}
int snake(char *A, char *B, int m, int n, int k, int j)
{
int i=j-k;
while(i < m && j < n && A[i+1] == B[j+1]){
i++;
j++;
}
return j;
}
```
The files
main.c   lcslib.h

Reference
S. Wu, U. Manber, G. Myers, and W. Miller, "An O(NP) sequence comparison algorithm," Information Processing Letters, Vol. 35, pp. 317-323, 1990.