爱泣鬼
《论算法设计中的分治与增量》，我会写！！ 
哦 ，kmp算法就是一种经典算法KMP算法一种改进的字符串匹配算法，由DEKnuth与VRPratt和JHMorris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称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(kk 满足下列关系式：(k #include #include using namespace std; inline void NEXT(const string& T，vector& next) { //按模式串生成vector，next(Tsize()) next[0]=-1; for(int i=1;i=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 next(Tsize()); NEXT(T，next); string::size_type index，count=0; for(index=0;index Length(t) then index := i - Length(t); end; End; BEGIN ClrScr; Write(s = ); Readln(str_s); Write(t = ); Readln(str_t); int_i := index( str_s， str_t ); if int_i <> 0 then begin Writeln( Found ， str_t， in ， str_s， at ， int_i， ); end else Writeln( Cannot find ， str_t， in ， str_s， ); END index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0
