← 都来码 / Dolaima← 例程索引objc/school/levenshtein_distance.m 原文

objc/school/levenshtein_distance.m · 1290 字节 · 下载原文

#include <stdio.h>
#include <string.h>

/* s, t: two strings; ls, lt: their respective length */
int levenshtein(const char *s, int ls, const char *t, int lt)
{
        int a, b, c;

        /* if either string is empty, difference is inserting all chars 
         * from the other
         */
        if (!ls) return lt;
        if (!lt) return ls;

        /* if last letters are the same, the difference is whatever is
         * required to edit the rest of the strings
         */
        if (s[ls - 1] == t[lt - 1])
                return levenshtein(s, ls - 1, t, lt - 1);

        /* else try:
         *      changing last letter of s to that of t; or
         *      remove last letter of s; or
         *      remove last letter of t,
         * any of which is 1 edit plus editing the rest of the strings
         */
        a = levenshtein(s, ls - 1, t, lt - 1);
        b = levenshtein(s, ls,     t, lt - 1);
        c = levenshtein(s, ls - 1, t, lt    );

        if (a > b) a = b;
        if (a > c) a = c;

        return a + 1;
}

int main()
{
        const char *s1 = "rosettacode";
        const char *s2 = "raisethysword";
        printf("distance between `%s' and `%s': %d\n", s1, s2,
                levenshtein(s1, strlen(s1), s2, strlen(s2)));

        return 0;
}