diff --git a/xneur/lib/misc/text.c b/xneur/lib/misc/text.c index f809c9d..2f34f7f 100644 --- a/xneur/lib/misc/text.c +++ b/xneur/lib/misc/text.c @@ -280,6 +280,30 @@ void del_final_numeric_char(char *word) word[len - offset] = NULLSYM; } +int levenshtein_dist(const int i, const int j, + const char *const s, const char *const t, + const int ls, const int lt, int d[ls+1][lt+1]) +{ + if (d[i][j] >= 0) return d[i][j]; + + int x; + if (i == ls) + x = lt - j; + else if (j == lt) + x = ls - i; + else if (s[i] == t[j]) + x = levenshtein_dist(i + 1, j + 1, s, t, ls, lt, d); + else { + x = levenshtein_dist(i + 1, j + 1, s, t, ls, lt, d); + + int y; + if ((y = levenshtein_dist(i, j + 1, s, t, ls, lt, d)) < x) x = y; + if ((y = levenshtein_dist(i + 1, j, s, t, ls, lt, d)) < x) x = y; + x++; + } + return d[i][j] = x; +} + int levenshtein(const char *s, const char *t) { int ls = strlen(s), lt = strlen(t); @@ -287,25 +311,5 @@ int levenshtein(const char *s, const char *t) memset(d, -1, sizeof(int) * (ls + 1) * (lt + 1)); - int dist(int i, int j) { - if (d[i][j] >= 0) return d[i][j]; - - int x; - if (i == ls) - x = lt - j; - else if (j == lt) - x = ls - i; - else if (s[i] == t[j]) - x = dist(i + 1, j + 1); - else { - x = dist(i + 1, j + 1); - - int y; - if ((y = dist(i, j + 1)) < x) x = y; - if ((y = dist(i + 1, j)) < x) x = y; - x++; - } - return d[i][j] = x; - } - return dist(0, 0); + return levenshtein_dist(0, 0, s, t, ls, lt, d); }