# Myers Algorithm(Edit-Distance, 1986)

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*d) time complexity
Description

The edit distance problem is to find the minimum cost of edit operations to transform one string to the other. Myers 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. The computation procedure is to calculate the furthest contour of distance 0, the furthest contour of distance 1, then distance 2, and so on. This algorithm performs well when the two strings are similar.

C source code
```int Myers_Alg(char *A, char *B, int m, int n)
{
//D=j-i
int *realV = new int[2*(m+n)];
int *V, i, j, D = 0;
V = realV + m + n;
memset(realV, -1, (2*(m+n))*sizeof(int));
V[1] = 0;

for(D = 0; D <= m+n; D++){
for(int k =- D;k <= D;k += 2){
if(k == -D || (k != D && V[k-1] < V[k+1])){
j=V[k+1];
}
else{
j=V[k-1]+1;
}
i = j-k;
while(j < n && i < m && B[j+1] == A[i+1]){
i++;
j++;
}
V[k] = j;
if(j >= n && i >= m){
delete [] realV;
return D;
}
}
}
}
```
The files
main.c   lcslib.h

Reference
E. W. Myers, "An O(ND) difference algorithm and its variations," Algorithmica, No. 1, pp. 251-266, 1986.