KMP关键是要求出字符串的特征向量，所谓匹配的最长前缀串，得出这个，其他的就好说了。http://www.faq-it.org/asp/">faq-it.org/asp/ 特别注意算法时间开销是O(n)，理解了其原因，算法的内涵就很清楚了。 详细细节请参考部分书籍，推荐：《数据结构与算法》许卓群张铭等2004高教版《TheArtofComputerProgramming》KnuthDE.vol1-3--------------------------------------------------------------- 这是我以前给别人讲的你先看看要是还不懂的话
提出来
严老的《数据结构》79页讲了基本的匹配方法，这是基础。先把这个搞懂了。80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。我们继续往下看：现在讨论一般情况。假设主串：s:'s(1)s(2)s(3)......s(n)';
模式串:p:'p(1)p(2)p(3)......p(m)'把课本上的这一段看完后，继续 现在我们假设主串第i个字符与模式串的第j（jk
满足下列关系式：(k#include
usingnamespacestd; inlinevoidNEXT(conststring&T,vector&next){
//按模式串生成vector,next(T.size())
next[0]=-1;
for(inti=1;i=0)
j=next[j];
//递推计算
if(T==T[j+1])next=j+1;
elsenext=0;
//
}
}
inlinestring::size_typeCOUNT_KMP(conststring&
S,
conststring&
T){
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vectornext(T.size());
NEXT(T,next);
string::size_typeindex,count=0;
for(index=0;index<S.size();++index){
intpos=0;
string::size_typeiter=index;
while(pos<T.size()&&iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
elsepos=next[pos-1]+1;
}
}//whileend
if(pos==T.size()&&(iter-index)==T.size())++count;
}//forend
returncount;}intmain(intargc,char*argv[]){
stringS="abaabcacabaabcacabaabcacabaabcacabaabcac";
stringT="ab";
string::size_typecount=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return0;}--------------------------------------------------------------- 书上是误导，不是说从前往后滑动多少字符，其实是从后往前滑动多少字符，虽然结果是从前往后计算的。只要你从后往前匹配就明白了。 |
