kmp模式匹配

Question

kmp算法中的next[]怎么求

Answer 1

void  NEXT(const  string&  T,vector<int>&  next)  
{  
       //按模式串生成vector,next(T.size())          
       next[0]=-1;                            
       for(int  i=1;i<T.size();i++  ){  
               int  j=next[i-1];  
               while(T[i]!=T[j+1]&&  j>=0  )  
                 j=next[j]  ;    //递推计算  
               if(T[i]==T[j+1])next[i]=j+1;      
               else  next[i]=0;    //  
       }          
}