模式串匹配---KMP

        朴素的的模式串匹配算法通常要在向前移动文本指针之后，回溯模式串指针，其效率为O(m*n)，而KMP算法则挖掘了一些模式串中的一些信息，来加快匹配的效率。

        KMP算法的紧随便是覆盖函数next。当模式串p[j]和文本串s[i]失配时，j指针不是简单的回溯，而是指向next[j]。

        覆盖函数next如何定义呢，它本质上是找到即是模式串p的前缀，又是它的后缀的最长字符串，即找到最大的k使得p[0]p[1]....p[k-1]=p[j-k]p[j-k+1]..p[j-1],然后将next[j]赋值为k。当然，这样的赋值并非最优化，注意到如果p[j]=p[k]，那next[j]和s[i]也必然失配，因此要递归的找到一个k使得p[j]!=p[k].

       以下是KMP算法的代码：

      

#include<iostream>
using namespace std;
void get_nextval(char const* ptrn, int plen, int* nextval)  
{  
    int i = 0;   
    nextval[i] = -1;  
    int j = -1;  
    while( i < plen-1 )  
    {  
        if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分  
        {  
            ++i;  
            ++j;  
            if( ptrn[i] != ptrn[j] )
                nextval[i] = j;     
            else  
                nextval[i] = nextval[j];  
        }  
        else                                 //循环的else部分  
            j = nextval[j];  
    }  
}  

void get_next(char const* ptrn, int plen, int* nextval)  
{  
    int i = 0;   
    nextval[i] = -1;  
    int j = -1;  
    while( i < plen-1 )  
    {  
        if( j == -1 || ptrn[i] == ptrn[j] )    //循环的if部分  
        {  
            ++i;  
            ++j;  
            nextval[i] = j;  
        }  
        else                         //循环的else部分  
            j = nextval[j];             //递推  
    }  
} 
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)  
{  
    int i = pos;  
    int j = 0;  
    while ( i < slen && j < plen )  
    {  
        if( j == -1 || src[i] == patn[j] )  
        {  
            ++i;  
            ++j;   //匹配成功，就++，继续比较。  
        }  
        else  
        {  
            j = nextval[j];             
        }  
    }  
    if( j >= plen )  
        return i-plen;  
    else  
        return -1;  
}     

int main()
{
	char p[9]={'a','b','a','a','b','c','a','b','a'};
	int  next[9];
	get_nextval(p,9,next);
	for(int i=0;i<9;++i)
		cout<<next[i]<<" ";
	cout<<endl;
}