Chpt.6.-字符串匹配-算法6.4-6.5-BM算法(bmSM)

当比对每个字串时，从右边开始匹配...

 

#include
#include
#include

 

/*Show usage*/

void usage(char * prog)
{
        printf("Usage: %s text pattern\n", prog);
        exit(123);
}

 

/*Get int dist[] for 'a' to 'z'*/

void bm_dist(char * patt, int patt_length, int * dist)
{
        char ch;
        int k;
        for(ch = 'a'; ch <= 'z'; ch ++) /*only 'a' to 'z' here*/
                dist[ch-97] = patt_length;

        for(k = 0; k <= patt_length -1; k ++)
                dist[patt[k] - 97] = patt_length - k - 1;

        printf("dist: ");
        for(k = 0; k < 26; k ++)
                printf("%d ", dist[k]);
        printf("\n");
}

 

/*Algorithm*/

void bm_sm(char * patt, char * text, int patt_length, int text_length, int * dist)
{
        int i, j, k;
        i = patt_length - 1; /*Start from text[patt_length-1]*/
        while(i < text_length)
        {
                j = patt_length - 1;
                k = i;
                while(j >= 0 && patt[j] == text[k])
                {
                        j --;
                        k --;
                }
                if(j < 0)
                {
                        printf("position %d\n", k + 1);
                        printf("text: %s\n", text);
                        printf("patn: ");
                        for(j = 1; j <= k +1; j ++)
                                printf(" ");
                        printf("%s\n", patt);
                        return;
                }
                else
                {
                        i = i + dist[text[i] - 97] - patt_length + j + 1;
                }
        }
                printf("Not match!\n");
}

int main(int argc, char * argv[])
{
        char * text = NULL;
        char * pattern = NULL;
        int dist[26];

 

        /*Check arguments*/
        if(argc != 3)
                usage(argv[0]);
        else
        {
                text = argv[1];
                pattern = argv[2];
        }

        printf("text: %s\n", text);
        printf("patn: %s\n", pattern);

        bm_dist(pattern, strlen(pattern), dist);
        bm_sm(pattern, text, strlen(pattern), strlen(text), dist);
        return 1;
}