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