# Wagner-Fischer Algorithm(Edit-Distance, 1974)

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(|A|*|B|) time complexity
Description

Wagner and Fischer first defined the simple version of the edit distance problem. Given two sequences (strings) A = a1a2a3... am and B = b1b2b3... bm, the edit distance problem is to find a series of edit operations with the minimum cost to transform A into B. The allowed edit operations include character insertion, character deletion and character replacement. They proposed a dynamic programming (DP) approach to solve the problem. Their algorithm calculates each cell of DP lattice in O(1) time and the size of DP lattice is O(nm), so the time complexity is O(mn).

C source code
```int WagnerFischer_Alg(char *stringA, char *stringB, int m, int n)
{
int i, j, **matrix;
int lcs = 0;
//memAllocMatrix
matrix = (int**) calloc(m + 2, sizeof(int*));

for (i = 0; i < m + 2; i++){
matrix[i] = (int*) calloc(n + 2, sizeof(int));
}

//initialize
for (i = 0; i <= m; i++){
matrix[i] = i;
}
for (i = 0; i <= n; i++){
matrix[i] = i;
}

// mainProcess
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
if (stringA[i] == stringB[j]){
matrix[i][j] = matrix[i - 1][j - 1];
}
else{
matrix[i][j] = min(min(matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + 2), matrix[i - 1][j] + 1);
}
}
}

lcs=(m + n - matrix[m][n]) / 2;
for (i = 0; i < m + 2; i++){
free(matrix[i]);
}
free(matrix);
return lcs;

}
```
The files
main.c   lcslib.h   WagnerFischer_Alg.exe

Reference
R. A. Wagner and M. J. Fischer, "The string-to-string correction problem," Journal of the ACM, Vol. 21, No. 1, pp. 168-173, 1974.