fuzzy_match.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>

static int
str_fzy(const char *str, const char *ptn)
{
    const char *pat = ptn;
    const char *beg = str;

    int run = 1;
    int score = 0;
    int remain = 0;

    assert(str);
    assert(ptn);
  
    for (;*str && *ptn; str++) {
        while (*str == ' ') str++;
        while (*ptn == ' ') ptn++;
        if (tolower(*str) == tolower(*ptn)) {
            score += run;
            run++, ptn++;
        } else score--, run = 1;
    }
    remain = (int)strlen(str);
    return (score + remain + str - beg) * (int)(ptn - pat) - remain;
}


struct match {int idx,val;};
static int
match_cmp(const void *f, const void *s)
{
    const struct match *a = (const struct match*)f;
    const struct match *b = (const struct match*)s;
    return b->val - a->val;
}
int main(void)
{
    static const char *files[] =  {
        "tau/src/main.c",
        "tau/src/ui.c",
        "tau/src/ui.h",
        "tau/src/sys.c",
        "tau/src/sys.h",
        "tau/src/res.c",
        "tau/src/res.h",
        "tau/src/util.c",
        "tau/src/cfg.h",
    };
    const int cnt = sizeof(files)/sizeof(files[0]);
    struct match m[sizeof(files)/sizeof(files[0])];
    
    int n = 0;
    for (int i = 0; i < cnt; ++i) {
        const int s = str_fzy(files[i], "util");
        if (!s) continue;        
        m[n++] = (struct match){.idx = i, .val = s};
    }
    qsort(m, n, sizeof(struct match), match_cmp);
    for (int i = 0; i < n; ++i)
        printf("%s(%d)\n", files[m[i].idx], m[i].val);
    return 0;
}