字符串比配问题，通过引入next[]而使效率提高

关于next[]数组，是对模式串的特征来构造的；

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

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

具体思想：

   根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]

   1)若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1;

   2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]。

模板：

求next[];

void getNext(char *p,int *next){    int j,k;    next[0]=-1;    j=0;    k=-1;    while(j<strlen(p)-1)    {        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]        {            j++;            k++;            next[j]=k;        }        else                   //p[j]!=p[k]            k=next[k];    }}

匹配字符串；

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];              

            //当匹配失败的时候直接用p[j_next]与s[i]比较，    

            //下面阐述怎么求这个值，即匹配失效后下一次匹配的位置    

        }    

    }    

    if( j >= plen )    

        return i-plen;    

    else    

        return -1;    

}    

杭电1711

这是一种看起来比较复杂的代码：

#include <string> 
#include <iostream>
#include<cstdio>
#include<cstring>
 
using namespace std; 
int src[1000501],prn[15001];
int nextval[15001];
template<typename S,typename T>
void get_nextval(S const* ptrn, T plen, T* nextval)   
{   
    int i = 0;  //注，此处与下文的代码实现二不同的是，i是从0开始的（代码实现二i从1开始）    
    nextval[i] = -1;   
    int j = -1;   
    while( i < plen-1 )   
    {   
        if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分   
        {   
            ++i;   
            ++j;   
            //修正的地方就发生下面这4行   
            if( ptrn[i] != ptrn[j] ) //++i，++j之后，再次判断ptrn[i]与ptrn[j]的关系   
                nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。   
            else   
                nextval[i] = nextval[j];   
        }   
        else                                 //循环的else部分   
            j = nextval[j];   
    }   
}   
 
 
template<typename S,typename T> 
int kmp_search(S const* src, T slen, S const* patn, T plen, T const* nextval, T pos)   
{   
    T i = pos;   
    T j = 0;   
    while ( i < slen && j < plen )   
    {   
        if( j == -1 || src[i] == patn[j] )   
        {   
            ++i;   
            ++j;   
        }   
        else   
        {   
            j = nextval[j];             
            //当匹配失败的时候直接用p[j_next]与s[i]比较，   
            //下面阐述怎么求这个值，即匹配失效后下一次匹配的位置   
        }   
    }   
    if( j >= plen )   
        return i-plen+1;   
    else   
        return -1;   
}   
 
int   main() 
{ 
 int t,slen,plen,i,j,a;
 
     scanf("%d",&t);
 while(t--)
 {
  scanf("%d%d",&slen,&plen);
  for(i=0;i<slen;i++)
   scanf("%d",src+i);
  for(j=0;j<plen;j++)
  scanf("%d",prn+j);
    get_nextval(prn, plen, nextval); 
     a= kmp_search(src, slen, prn, plen, nextval, 0);
 printf("%d\n",a);
 }
  
    return 0; 
}  

杭电1686

#include <string> 
#include <iostream>
#include<cstdio>
#include<cstring>
 
using namespace std; 
char src[1000500],prn[10050];
int nextval[10050],slen,plen;

void get_nextval( int plen)   
{   
    int i = 0;  //注，此处与下文的代码实现二不同的是，i是从0开始的（代码实现二i从1开始）    
    nextval[i] = -1;   
    int j = -1;   
    while( i <= plen-1 )   
    {   
        if( j == -1 || prn[i] == prn[j] )   //循环的if部分   
        {   
            i++;   
            j++;   
            //修正的地方就发生下面这4行   
            //++i，++j之后，再次判断ptrn[i]与ptrn[j]的关系   
                nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。      
        }   
        else                                 //循环的else部分   
            j = nextval[j];   
    }   
}   
 
 
int kmp_search( int slen,int plen)   
{   
    int i = 0;   
    int j = 0,count=0;   
    while ( i < slen )   
    {   
        if( j == -1 || src[i] == prn[j] )   
        {  
            i++;   
            j++;
        }   
        else   
           j = nextval[j];             
               
       if(j==plen)   
     count++;
    }   
      
        return count;     
}   
 
int   main() 
{ 
 int t,i,j,a;

    scanf("%d",&t);
     while(t--)
 {
  scanf("%s%s",prn,src);
     slen = strlen(src);
  plen = strlen(prn);
    
    get_nextval( plen); 
    a= kmp_search(slen,plen);

  printf("%d\n",a);
 
    
 }
  
    return 0; 
}