数据结构-KMP算法

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。

在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

对于next[]数组的定义如下：

1)next[j]=-1  j=0

2)next[j]=max k:0

3)next[j]=0  其他

KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

KMP算法的关键在于求算next[]数组的值，即求算模式串每个位置处的最长后缀与前缀相同的长度。

 

源代码：
#include
#include

#define MAXSIZE 1024

void get_next(char *T, int *next)

{

        int     i=1, j=0;

        next[0]=-1;

        while(i < strlen(T)){

                if(j == -1 || T[i] == T[j]){

                        i++; j++; next[i]=j;

                }else{

                        j=next[j];

                }

        }

}

int get_index(char *S, char *T, int pos)

{

        int     next[MAXSIZE]={0};

        int     i=pos, j=0;

        int     slen=strlen(S);

        int     tlen=strlen(T);

        get_next(T, next);

        for(i=0; i

                printf("%c,%d\n", T[i],next[i]);

        i = pos;

        while(i < slen && j < tlen){

                if(j == -1 || S[i] == T[j]){

                        printf("匹配:[%d][%d]\n", i, j);

                        i++; j++;

                }else{

                        printf("失配:[%d][%d][%d]\n", i, j, next[j]);

                        j = next[j];

                }

        }

        if(j >= tlen)

                return i-tlen;

        else

                return -1;

}

int main()

{

        char    S[]="acabaabaabcacaabc";

        char    T[]="abaabcac";

        printf("index[%d]\n", get_index(S, T, 0));

        return 0;

}