BM

/*a中存放bad char下一次对齐的位置*/
void getbc(int a[], int n, const char *s)
{
        int i;
        unsigned char c;
        size_t len = strlen(s);
        for (i = 0; i < n; i++) {
                a[i] = -1;
        }

        for (i = 0; i < len - 1; i++) { //不修改最后一个位置
                c = (unsigned char)s[i];
                a[c] = i;
        }
}

/*b中存放b[n-1]要下一次要对齐的位置*/
void getsuf(int b[], int n, const char *s)
{
        int i, first;
        first = -1;
        for (i = n-2; i >= 0; i--) {
                b[i] = -1;
                if (s[i] == s[n-1]) {
                        first = i;
                }
        }
        b[n-1] = n-2;
        for (i = n-2; i >= 0; i--) {
                if (s[i] == s[n-1]) {
                        int j, k;
                        j = i - 1;
                        k = n - 2;
                        while (s[j] == s[k]) {
                                j --;
                                k --;
                                printf("%c-%c\n", s[j], s[k]);
                                if (j < 0)
                                        break;

                        }
                        if (b[k] == -1) {
                                b[k] = i;
                        }
                        printf("i = %d\n", i);
if (j == -1 && i == first) { //最后一个且可以匹配到末尾
                                while (k-- > 0) {
                                        if (b[k] == -1)
                                                b[k] = i;
                                }
                        }
                }
        }
}
void bm(const char *str, const char *pat)
{
        int n, index;
        int *suf;
        int *bc;

        n = strlen(pat);

        suf = malloc(n * sizeof(int));
        bc = malloc(256 * sizeof(int));
        getbc(bc, 256, pat);
        getsuf(suf, n, pat);

        index = n - 1;
        while (index < strlen(str)) {
                int i, j;
                i = index;
                j = n - 1;
                while (str[i] == pat[j] && j >= 0) {
                        i--;
                        j--;
                }
                if (j == -1) {
                        index = index + 1;
                        printf("match at pos %d\n", i + 1);
                } else {
                        int max;
                        max = j - bc[str[index]];
// max = n - 1 - bc[str[index]]; //horspool
                        max = max > n - 1 - suf[j] ? max : n - 1 - suf[j];
                        index = index + max;
                }
        }
}