| 词条 | kmp算法 |
| 释义 | § kmp算法 一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。 完全掌握KMP算法思想 学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。 如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。) 严老的《数据结构》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(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较 此时，s(i)≠p(j), 有 主串： S(1)…… s(i-j+1)…… s(i-1) s(i) …………. || (相配) || ≠(失配) 匹配串： P(1) ……. p(j-1) p(j) 由此，我们得到关系式 ‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’ 由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j), ‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’ 即： 主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) …………. || (相配) || || ?(有待比较) 匹配串： P(1) p(2) …… p(k-1) p(k) 现在我们把前面总结的关系综合一下 有： S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) …… || (相配) || || || ≠(失配) P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j) || (相配) || || ?(有待比较) P(1) p(2) ……. p(k-1) p(k) 由上，我们得到关系： ‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’ 接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码) K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。 课本83页不是有个例子吗？就是 图4.6 你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。 然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！ § 附 KMP算法查找串S中含串P的个数count #include <iostream> #include <stdlib.h> #include <vector> using namespace std; inline 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!=T【j+1】&& j>=0 ) j=next【j】 ; //递推计算 if(T==T【j+1】)next=j+1; else next=0; // } } inline string::size_type COUNT_KMP(const string& S, const string& T) { //利用模式串T的next函数求T在主串S中的个数count的KMP算法 //其中T非空， vector<int> next(T.size()); NEXT(T,next); string::size_type index,count=0; for(index=0;index<S.size();++index){ int pos=0; string::size_type iter=index; while(pos<T.size() && iter<S.size()){ if(S【iter】==T【pos】){ ++iter;++pos; } else{ if(pos==0)++iter; else pos=next【pos-1】+1; } }//while end if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count; } int main(int argc, char *argv【】) { string S="abaabcacabaabcacabaabcacabaabcacabaabcac"; string T="ab"; string::size_type count=COUNT_KMP(S,T); cout<<count<<endl; system("PAUSE"); return 0; } |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。