暴力匹配，kmp，sunday, shift-and, shift-or, 字符串匹配算法，单模匹配, 多模匹配

字符串匹配算法

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

#define TEST(func, s, t) printf("%s: %s->%s = %d
", #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;
}

// shift-and算法
int shift_and(char *s, char *t) {
        int p = 0, b[255] = {0};
        for (int i = 0; t[i]; i++) b[t[i]] = (b[t[i]] | 1) << i; 
        for (int i = 0; s[i]; i++) {
                p = (p << 1 | 1) & b[s[i]];
                printf("%c==%d
", s[i], p);
                if (p & (0x01 << strlen(t) - 1)) return i - strlen(t) + 1;
        }
        return -1;
}

// shift-or算法
int shift_or(char *s, char *t) {
        int p = 0, b[255];
        memset(b, -1, sizeof(int) * 255);
        for (int i = 0; t[i]; i++) b[t[i]] ^= 1 << i; 
        for (int i = 0; s[i]; i++) {
                p = (p << 1) | b[s[i]];
                printf("%c==%d
", s[i], p);
                if (~p & (0x01 << strlen(t) - 1)) return i - strlen(t) + 1;
        }
        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);
                TEST(shift_and, s, t);
                TEST(shift_or, s, t);
        }
        return 0;
}