KMP模式字符串匹配算法类封装

KMP模式字符串匹配算法类封装：

 

class KMP{
private:
     char* p_;                                      //模式串； 
     int const plen_;                            //模式串长度； 
     int* next_;                                    //模式串的nextval数组； 

public: 
     KMP(void):p_(0),plen_(0){};         //构造函数；

     KMP(char const* p,int len):plen_(len){              //重载构造函数；
          p_=(char*)malloc(len*(sizeof(int)+sizeof(char))};
          next_=reinterpret_cast<int*>(p_+len);
          memcpy(p_,p,len);
          compute_nextval(next_,p,len);       //得到next_数组； 
     }

     ~KMP(void){ ::free(p_);}          //析构函数；

     int find_in(char const* t,int len){     //返回首次出现的相对位置；t为目标字符串；                            
         int j=-1; int i=-1;
         while((j<plen_)&&(i<len)){
              if((j==-1)||(p_[j]==t[i])){++i; ++j;}
              else j=next_[j];
         }
         if(j==plen_) return i-j;
         else return -1;
     }

     std::vector<int> find_all(char const* t,int len){     //返回所有出现的相对位置；
         std::vector<int> result;
         int j=-1; int i=-1;
     start:
         while((j<plen_)&&(i<len)){
             if((j==-1)||(p_[j]==t[i])){++i; ++j;}
             else j=next_[j];
         }
         if(j==plen_) result.push_back(i-j);
         if(i<len){
               j=next_[j-1];
               goto start;
         }
         else return result;
     }

     void rebuild(char const* p,int len)                //重新设置模式串；
     { this->~KMP(); new(this)KMP(p,len); }

     void compute_nextval(int* nextval,char const* p,int len){       //得到next_数组；
          int j=0;
          int q=nextval[0]=-1;                  //q==next[j]; 
          --len;
          while(j<len)                   //此循环计算nextval[j+1]; 
             if(q==-1||p[j]==p[q])           //找到next[j+1];计算nextval[j+1]; 
                 if(p[++j]!=p[++q])          //q==next[j]; 
                     nextval[j]=q;
                 else 
                     nextval[j]=nextval[q];
             else                             //没有找到next[j+1]继续尝试 
                  q=nextval[q];           //本该是q=next[q]; 
     }      
};