• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

字符串匹配算法,暴力匹配,kmp,sunday

开发技术 开发技术 3小时前 1次浏览

字符串匹配算法

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

#define TEST(func, s, t) printf("%s: %s->%s = %dn", #func, s, t, func(s, t))

int next[100];
//暴力匹配算法
int brue_force(const char *s, const char *t) {
        int i, j;
        for (i = j = 0; t[i] && s[j + i]; ) {
                if (t[i] == s[j + i] && ++i) continue;
                i = 0, ++j;
        }
        return !t[i] ? j : -1;
}

int getNext(const char *t, const char s, int j) {
        while (j ^ -1 && t[j + 1] ^ s) j = next[j];
        if (t[j + 1] == s) ++j;
        return j;
}
// kmp算法
int kmp(const char *s, const char *t) {
        next[0] = -1;
        for (int i = 1, j = -1; t[i]; i++) next[i] = j = getNext(t, t[i], j);
        for (int i = 0, j = -1; s[i]; i++) {
                j = getNext(t, s[i], j);
                if (!t[j + 1]) return i - j;
        }
        return -1;
}

// sunday算法
int sunday(const char *s, const char *t) {
        int d[255], tl = strlen(t);
        memset(d, -1, sizeof(d));
        for (int i = 0; t[i]; i++) d[t[i]] = tl - i;
        for (int i = 0, j = 0; j + tl <= strlen(s); ) {
                while (s[i + j] == t[i] && t[i] && ++i) continue;
                if (!t[i]) return j;
                j += d[s[j + tl]] < 0 ? tl : d[s[j + tl]];
                i = 0;
        }
        return -1;
}

int main() {
        char s[100] = {0}, t[100] = {0};
        while(~scanf("%s%s", s, t)) {
                TEST(brue_force, s, t);
                TEST(kmp, s, t);
                TEST(sunday, s, t);
        }
        return 0;
}


程序员灯塔
转载请注明原文链接:字符串匹配算法,暴力匹配,kmp,sunday
喜欢 (0)