kmp算法

kmp算法介绍：http://www.matrix67.com/blog/archives/115

/***********************************************************
 * kmp字符串匹配算法
 **********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(int argc,char *argv[])
{
        int m;
        int n;
        int *pi = NULL;
        int ret = 0;
        int i;
        
        if(argc != 3)
        {
                printf("usage:%s string string\n",argv[0]);
                exit(-1);
        }
                
        m = strlen(argv[1]);
        n = strlen(argv[2]);
        
        if(m < n)
        {
                printf("the first string must be longer than the second string\n");
                exit(-1);
        }
        
        pi = (int *)malloc(sizeof(int)*n);
        if(pi == NULL)
        {
                printf("malloc error!\n");
                exit(-1);
        }
        
        getPI(argv[2],n,pi);
        
        ret = kmp(argv[1],m,argv[2],n,pi);
        if(ret < 0)
        {
                exit(-1);
        }
        else
        {
                printf("match at %d\n",ret);
        }
        
        free(pi);
        pi = NULL;
        
        return 0;
}

int getPI(char *src,int len,int *arr)
{
        int i = 0;
        int j = 0;
        
        arr[0] = -1;
        for(i = 1; i < len; i++)
        {
                j = arr[i-1];
                while(j>=0 && src[i]!=src[j+1])
                {
                        j = arr[j];
                }
                
                arr[i] = (src[i]!=src[j+1] ? j : j + 1);
        }
        
        return 0;
}

int kmp(char *src,int len_src,char *dest,int len_dest,int *arr)
{
        int i = 0;
        int j = 0;
        
        for(i = 0; i < len_src; i++)
        {
                //printf("\n%s\n%s\n",src+i,dest+j);

                while(src[i] != dest[j] && j > 0)
                {
                        j = arr[j-1] + 1;
                        //printf("%s\n",dest+j);

                }
                
                j = (src[i] == dest[j]) ? j + 1 : j ;
                if( j == len_dest )
                {
                        return i-j+1;
                }
        }
        
        return -1;
}