Merge commit 'refs/top-bases/girocco' into girocco
[git/repo.git] / levenshtein.c
blobdb52f2c205029229c7eedc8fbc042d3945436803
1 #include "cache.h"
2 #include "levenshtein.h"
4 int levenshtein(const char *string1, const char *string2,
5 int w, int s, int a, int d)
7 int len1 = strlen(string1), len2 = strlen(string2);
8 int *row0 = xmalloc(sizeof(int) * (len2 + 1));
9 int *row1 = xmalloc(sizeof(int) * (len2 + 1));
10 int *row2 = xmalloc(sizeof(int) * (len2 + 1));
11 int i, j;
13 for (j = 0; j <= len2; j++)
14 row1[j] = j * a;
15 for (i = 0; i < len1; i++) {
16 int *dummy;
18 row2[0] = (i + 1) * d;
19 for (j = 0; j < len2; j++) {
20 /* substitution */
21 row2[j + 1] = row1[j] + s * (string1[i] != string2[j]);
22 /* swap */
23 if (i > 0 && j > 0 && string1[i - 1] == string2[j] &&
24 string1[i] == string2[j - 1] &&
25 row2[j + 1] > row0[j - 1] + w)
26 row2[j + 1] = row0[j - 1] + w;
27 /* deletion */
28 if (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)
29 row2[j + 1] = row1[j + 1] + d;
30 /* insertion */
31 if (row2[j + 1] > row2[j] + a)
32 row2[j + 1] = row2[j] + a;
35 dummy = row0;
36 row0 = row1;
37 row1 = row2;
38 row2 = dummy;
41 i = row1[len2];
42 free(row0);
43 free(row1);
44 free(row2);
46 return i;