Chpt6-字符串匹配-算法6.2-6.3KMP算法(KMPSM)

SimpleSM每次移动一个字符，而KMP算法每次移动一段距离~

 

#include
#include
#include

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

 

/*Caculate the int next[] */

void kmp_next(char * patt, int patt_length, int * next)
{
        int i, j;
        next[0] = 0;

        for(j = 1; j < patt_length; j ++)
        {
                i = next[j -1];

                while((i > 0) && (patt[i] != patt[j]))
                        i = next[i-1];

                if(patt[j] == patt[i])
                        next[j] = i + 1;
                else
                        next[j] = 0;
        }
}

 

/*Algorithm*/

void kmp_sm(char * patt, char * text, int patt_length, int text_length, int * next)
{
        int i, j = 0;
        int k;
        for(i = 0; i < text_length; i ++)
        {
                while((j > 0) && patt[j] != text[i])
                        j = next[j - 1];

                if(patt[j] == text[i])
                        j ++;

                if(j == patt_length) /*return the position*/
                {
                        printf("position %d\n", i - j + 1);
                        printf("text: %s\n", text);
                        printf("patn: ");
                        for(k = 1; k <= i - j + 1; k ++)
                                printf(" ");
                        printf("%s\n", patt);
                        return;
                }
        }
        printf("Not match!\n");
}

 

int main(int argc, char * argv[])
{
        char * text = NULL;
        char * pattern = NULL;
        int * next = NULL;
        if(argc != 3)
                usage(argv[0]);
        else
        {
                text = argv[1];
                pattern = argv[2];
        }
        printf("text: %s\n", text);
        printf("patn: %s\n", pattern);

        next = (int *)malloc((strlen(pattern)) * sizeof(int));
        kmp_next(pattern, strlen(pattern), next);
        kmp_sm(pattern, text, strlen(pattern), strlen(text), next);
        free(next);
        return 1;
}