1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
/*
* Copyright (c) 2026, Chloe M., et al.
* Provided under the BSD-3 clause.
*/
#include <stdio.h>
#include <string.h>
/*
* Compute the levenshtein distance between two strings
*
* @s1: First string to compare
* @s2: Second string to compare
* @l1: Length of first string to compare
* @l2: Length of second string to compare
*/
static int
lev_distance(const char *s1, const char *s2, size_t l1, size_t l2)
{
int matrix[l1 + 1][l2 + 1];
int i, j, c1, c2;
int delete, insert;
int subst, min;
for (i = 0; i <= l1; ++i) {
matrix[i][0] = i;
}
for (i = 0; i < l2; ++i) {
matrix[0][i] = i;
}
for (i = 1; i <= l1; ++i) {
c1 = s1[i - 1];
for (j = 1; j <= l2; ++j) {
c2 = s2[j - 1];
if (c1 == c2) {
matrix[i][j] = matrix[i-1][j-1];
} else {
delete = matrix[i-1][j] + 1;
insert = matrix[i][j-1] + 1;
subst = matrix[i-1][j-1] + 1;
min = delete;
if (insert < min)
min = insert;
if (subst < min)
min = subst;
matrix[i][j] = min;
}
}
}
return matrix[l1][l2];
}
int
main(int argc, char **argv)
{
char *s1, *s2;
size_t l1, l2;
if (argc < 3) {
printf("fatal: expected s1 and s2\n");
return -1;
}
s1 = argv[1];
s2 = argv[2];
l1 = strlen(s1);
l2 = strlen(s2);
printf("%d\n", lev_distance(s1, s2, l1, l2));
return 0;
}
|
