c语言实现BM算法

1.源码实现

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

#define KEYSIZE 256

/*求坏字符偏移*/
void PreBmBc(char *x, int m, int *bc)
{
    int i;

    for(i=0; i<KEYSIZE; i++)
    {
        bc[i] = -1;
    }

    for(i=0; i<m; i++)
    {
        bc[x[i]] = i;
    }

    /*for(i=0; i<m; i++)
    {
        printf("bc[%c]=%d\n", x[i], bc[x[i]]);
    }*/
}

/*求好后缀偏移*/
int PreBmGs(char *pat, int n, int *sf, int *sfl)
{
    int m = n / 2;
    int u = 0;
    int i;
    int j;
    int k = 0;

    for(i=0; i<n; i++)
    {
        sf[i] = -1;
        sfl[i] = 0;
    }

    for(i=0; i<m; i++)
    {
        for(j=0; j<n-1-i; j++)
        {
            u = 1;

            for(k=0; k<=i; k++)
            {
                if(pat[j+k] != pat[n-1-i+k])
                {
                    u = 0;
                    break;
                }
            }

            if(u)
            {
                sf[n-1-i] = j;
                sfl[n-1-i] = i+1;
            }
        }
    }

    for(i=n-2; i>=0; i--)
    {
        if(sf[i+1] < i && sfl[i] < sfl[i+1])
        {
            sf[i] = sf[i+1];
            sfl[i] = sfl[i+1];
        }
    }

    for(i=0; i<n; i++)
    {
        if(sf[i] == -1)
        {
            sf[i] = n - 1;
        }
        else
        {
            /*printf("sf=%d\n", sf[i]);*/
            sf[i] = n - sfl[i] - sf[i];
        }
    }

    /*for(i=0; i<n; i++)
    {
        printf("sf[%d]=%d, sfl[%d]=%d\n", i, sf[i], i, sfl[i]);
    }*/

    return 0;
}

int BM(char *str, int n, char *pat, int m, int *bc, int *sf)
{
    int c, d;
    int i = 0;
    int j = m-1;
    int k = 0;
    int l = 0;

    /*printf("str=%s\n", str);
    printf("pat=%s\n", pat);

    printf("i=%d, j=%d\n", i, j);*/

    while(i+j < n)
    {
        /*printf("str[%d+%d]=%c, pat[%d]=%c\n", i, j, str[i+j], j, pat[j]);*/

        if(str[i+j] != pat[j])
        {
            c = j - bc[str[i+j]];
            d = 0;

            if(j+1 < m)
            {
                /*printf("sf[%d]=%d\n", j+1, sf[j+1]);*/
                d = sf[j+1];
            }

            /*printf("c=%d, d=%d\n", c, d);*/

            /*偏移值为坏字符和好后缀的最大值*/
            i += (c > d ? c : d);

            j = m - 1;

            l++;
        }
        else
        {
            j--;
        }

        if(j == -1)
        {
            /*printf("%d\n", i);*/
            break;
        }
    }

    if(j != -1)
    {
        return -1;
    }

    return i;
}

int main()
{
    FILE *fp;
    char str[4096] = "abcacabbcabccabc";
    char pat[1024] = "your";
    int bc[256];
    int sf[256];
    int sfl[256];

    int n = strlen(str);
    int m = strlen(pat);
    int u;
    int k = 0;

    PreBmBc(pat, m, bc);
    PreBmGs(pat, m, sf, sfl);

    /*u = BM(str, n, pat, m, bc, sf);

    printf("u=%d\n", u);*/

    fp = fopen("1.txt", "r");

    memset(str, 0x00, sizeof(str));

    while(fgets(str, 2048, fp) != NULL)
    {
        n = strlen(str);

        k++;

        /*printf("BM begin %d\n", k);*/

        u = BM(str, n, pat, m, bc, sf);

        /*printf("BM end\n");*/

        if(u >= 0)
        {
            printf("%d\n", u);
        }

        memset(str, 0x00, sizeof(str));
    }

    fclose(fp);

    return 0;
}

2.编译源码

$ gcc -o example examle.c -std=c89

4.运行及其结果

$ ./example
839
378
744