完全掌握KMP算法思想

1、完全掌握KMP算法思想学过数据结构的人，都对 KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得 头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解 KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。)严老的数据结构79页讲了基本的匹配方法，这是基础。先把这个搞懂了。80页在讲KMP算法的开始先举了个例子，让我们对 KMP的基本思想有了最初的认 识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。我们继续往下看： 现在讨论一般情况。假设主串：s: 's(1)s(2) s(3

2、),s(n)' 模式串:p： 'p(1)p(2)p(3),.p(m)把课本上的这-现在我们假设一 g/t去土 u 以有兀落，主串第i继续个字符与模式串的第j(j<=m)个字符'失配后，主串第i个字符与模式串的第k(k<j)个字符继续比较此时，s(i)乒p(j),有主串：S(1),s(i- j+1), s(i| (相配)匹配串：P(1),.由此，我们得到关系式'p(1) p(2) p( 3),.p(j-1)'-1)|p(j-1) p(j)= s(is(i) ,.头(失配)-j+1),s(i-1)'由于s(i)乒p(j)，接下来 s(i)

3、将与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) ,.| (相配)|?(有待比较)匹配串：Pp(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

4、-k+1) p(j-k+2)P(j-1) P(j)| (P(1)P(2)相配）|?(有待比较）p(k-1) P(k)由上，我们得到关系：'ppp(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你照着源程序，看着那个例子慢慢的推出它来。看

5、看你做的是不是和课本上正确的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)/ 按模式串生成

6、 vector,next(T.size()next0=-1;for(int i=1;i<T.size();i+ )int j=nexti-1;while(Ti!=Tj+1&& j>=0 )j=nextj ; /递推计算if(Ti=Tj+1)nexti=j+1;else nexti=0; /)inline string:size_type COUNT_KMP(const string& S,const string& T)/ 利用模式串T的next函数求T在主串S中的个数count的KMPB法/ 其中T非空，vector<int> next

7、(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(Siter=Tpos)+iter;+pos;elseif(pos=0)+iter;else pos=nextpos-1+1;/while endif(pos=T.size()&&(iter-index)=T.size(

8、)+count; /for endreturn 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;关于KMP算法当中的next函数首先先贴出KMP算法的框架代码，这段代码使用 C语言当中的字符串数据结构，因此字符

9、串当中第一个字符的下标为零。int Index(const char * str1,const char * str2,int pos)(int * nextFunc = get_next(str2);int strLen = strlen(str1);int subLen = strlen(str2);int i = pos,j = 0;while (i < strLen && j < subLen)(if (j = -1 | str1i = str2j)(i+;j+; elsej = nextFuncj;if (j = subLen)return i - sub

10、Len;return -1;相比较那种最简单的算法而言这里的神奇之处在于一个next函数，由于这个 next函数的存在导致我们在模式匹配过程当中某个字符出现失配的情况时不再需要回溯主串当 中的指针i到开始匹配时的位置。所有的数据结构或者算法的书都告诉我们说，之所以不需 要回溯这个i指针是因为在匹配过程当中产生了一些附加的信息，利用这些附加信息就可以得到这样的性能改进。首先我们必须搞清楚这个神奇的next函数的含义。nextj=k这样一个式子表示的含义是，当主串当中第i个元素与模式串当中第j个元素不匹配时我们应该保持i指针不动而将模式串当中的j指针移动到k这个位置，然后再比较主串的第i个元素与模

11、式串的第k个元素是否匹配，匹配当然没话说照最传统的算法移动两个指针比较下一个元素或者得到完 全匹配的结果，不匹配那么再做那个动作，也就是求nextk= ?,然后再比较。之所以存在这么一个 next函数是因为，如果说主串与模式串在匹配过程当中主串 的第i个元素与模式串的第j个元素不同，那么隐含的意义是主串的从第i-j+1个元素到第i-1个元素与模式串的第1个元素到第j-1个元素是相同的。那么如果说这样不能达到最后全部匹配的结果也就是上面讲的主串i !=模式串j,那么我们应该从主串的i-j+1到i-1这个字串当中从后到前寻找一个最大子串与模式串的第1到j-1这个字串的从第一个到某个元素的最大子串完

12、全匹配。而我们又知道主串中第i-j+1个元素到第i-1个元素的子串事实上就是模式串当中第1个元素到第j-1个元素所形成的子串。next函数所完成的工作就是这个寻找 匹配的工作，他的返回值就是这个子串的最后一个元素的下一个位置。为什么是这个位置, 前面讲的很清楚，就是说既然前面那一串匹配，那么接下来要比较的就是这个位置的元素。 下面开始描述next函数的求法。从上面的描述我们可以知道next函数的值完全只与模式串相关而与主串是什么样子的没有任何关系，因此来说对于每个模式串都有一个唯一的next串值。求法是这样，如果说自变量为0也就是说第一个元素的next值固定为-1（-1的意思是说，主串的当前位

13、置元素与模式串第一个元素的前一个元素匹配，隐含意义是讲主串指针必须往后移一位再与模式串的第一个元素比较）；如果nextj = k也就是说模式串的第1个元素到第k个元素与第j-k+1个元素到第j-1个元素相等相等（可以按照上面的方法推出到主串上哪几个元素），而且有模式串j=模式串k那么可以得到nextj+1 = k+1（这里的原理显而易见）；如果不等那么就 求另外一个最大子串，方法就是j = nextk,然后再回到上面的比较。而其他的情况就视作next值为0（事实上只有求j=1时的next值才会出现，所以 next值的前两个元素固定是0和1）。具体算法如下： int * get_next(con

14、st char * str)(int strLen = strlen(str);int * nextFunc = new intstrLen;if (!nextFunc)return 0;nextFunc0 = -1;int i = 0,j = nextFunci;while (i < strLen)(if (j = -1 | stri = strj)(i+;j+;nextFunci = nexti-1 + 1;elsej = nextFuncj;return nextFunc;注：本文所有的串表示方法都是C语言的默认表示方法，也就是第一个兀素的下标为0本文来 自 CSDN 博客， 转

15、载请标 明 出 处2 KMP算法:KMP算法是由D.E.Knuth （克努特），J.H.Morris （莫里斯），V.R.Pratt （普拉特）等人共同提 出的，该算法主要消除了主串指针（i指针）的回溯，利用已经得到的部分匹配结果将模式串右滑尽可能远的一段距离再继续比较，从而使算法效率有某种程度的提高，O（n+m）。先从例子入手（p82 ）：4云第一趟主串模式acabaabaabcacaabcabaabcac个 j=2 next2=1按 Brute-Force 算法 i=i-j+2=2-2+2=2,j=1第二趟主串 模式11=2acabaabaabcacaabc=1a tnezt 11= O1

16、按 Brute-Force 算法 i=i-j+2=2-1+2=3,j=1产8acabaabaabcacaabc abaabcacf j=6 nextfi=3按Brute-Force算法i=i-j+2=8-6+2=4,j=1,但从已匹配的情况看， 模式串在t6即"c”前 的字符都是匹配的，再看已匹配的串" abaab" ,t1t2与t4t5相同，那么，因为 t4t5 与原串s6s7匹配，所以t1t2必然与原串s6s7匹配，因此说t3可以直接与s8匹配, 按 KMP 算法 i=8,j=34 3* >第四趟主串模式acabaabaabcacaabc abaabca

17、c| j=3 > f J=9匹配成功。从上例看出在匹配不成功时，主串指针i不动，j指针也不回到第一个位置，而是回到一个恰当的位置，如果这时让 j指针回到第一个位置，就可能错过有效的匹配，所以 在主串指针i不动的前提下，j指针回到哪个位置是问题的关键，既不能将 j右移太大，而 错过有效的匹配，另一方面，又要利用成功的匹配，将j右移尽可能地大，而提高匹配的效率，因此问题的关键是寻找模式串自身的规律。c » . ttll%1/设 S = "S1满足：(1) Sj i(2) ”仕所以：直接比较si和tkS2Si -1t"Sn"，t="ti t2*

18、 tjf"t j k it j k 2 t j1 " (1 k j )/若不满足(2),直接比较Sj和0/设 s=" ss2 . Sn”, t= " i t2 . tm ”，在匹配过程中，当Si丰 tj(i < i< n-m+1,1 < j< m)时，存在(前面的j-1个字符已匹配)：i-j+1 . Si-1一 1 tt2 . tj-1(1)若模式中存在可互相重叠的最长的真子串、满足:"ltt2 . tk-1 "=" j-k+1 tj-k+2 . tj-1 "(2)其中真子串最短可以是ti

19、,即tit2-i (k>1),最长的是titj-1-1 (k<j)，所以(1<k<j)。由(1)式说明模式串中的子串” 1t t2 . tk-1 ”已和主串” iSk+1 Si-k+2 . Si-1 ”匹配，下一次可直接比较Si和tk，若不存在(2)式，则结合(1)式说明在"1 t. tj-1 ”中不存在任何以t1为首字符 子串与i-j+1Si-j+2 . Si-1”中以Si-1为末字符的匹配子串，下一次可直接比较Si和t1。主串指针的不回溯，。例(p82):主串a c a b a a b a a b c a c a a b c模式a b a a b c a

20、c现在的问题是要求 next函数，next(j)的作用是，当Si与tj匹配失败时，Si与tnext(j)匹配。next函数的定义如下：$图形拖放IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII模式串t的next函数：0j = 1next(j)= !maxk|(1< k< j)八七tsL't-r t"当此集会不空J其它情况当Si和tj匹配失败时,

21、§与tnext(j)匹配。 jnexi( j )IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII例：求abaabcad的爬M/)next(l = 0-1 anext(31 = 1ab- 2TTbanext(5) - 2abaanext(6) -3abaabnext(J = 1abaabcnext(81 = 2TT6aabc a例：next(1) =0 next(2) = 1 next(3) =1

22、 next(4) = 2 next(5) =2 next(6) =3 next(7) = 1next(8) = 2求"abaabcac"的 next( j)a a b a b a b a b a b a b例：根据定义手工求模式aaaaabaabcaabc aa b a a b c a c的 next 函数(1) next(1)=0(2) next=1 (t1 =a中不存在真子串，即不存在k满足1<k<2)(3) next(3)=1(t t2=a b没有重叠真子串)(4) next(4)=2 (t .t3=a b a有重叠真子串t1和t3,所以k=2)(最后一位

23、与前几位是否有 重叠的串)(5) next(5)=2(t.t4=ab aa有重叠真子串 t和t4,所以k=2)(6) next(6)=3(t1.t5=ab aa b有重叠真子串 t1t2和t3t4,所以 k=3)(7) next7)=1(t.t6=ab aa bc没有重叠真子串)(8) next(8)=2(t.t7=ab aa bc a有重叠串 t和t7,所以k=2)求模式a b a a b c a c的next函数的算法： 因为已知next(1)=0，只要找出next(j+1 )与next(j)之间的关系，就可以求出模式串所有next(j)。/ 图形拖放开始 /初始算法：初值 next (1

24、)= 0;设next(j)=k,于是有:"titk-i"="tj-k+i“ 如"，(2-1)若tj = tk必然有："titk-itk"="tj-k妇t”j所以 next(j 1) = k 1 = next(j) 1;(2-2)若 tj，tk又因为next(k广k'必然有："t10-1"="顷'1t"'(2- 2- 1)若tj = tknext(j 1) = k' 1 = next(k') 1 =next(next( j) 1;(2- 2- 2)

25、若tj , tk'重复(2- 2)直到不存在k(n),则nextj 1)= 1./图形拖放结束/-Z-求next函数算法(p83):(非甬好的解释和例子)void get_next(sstring T, int &next)(求模式串T的next函数值并存入数组 nextoj=1; k=nextj=0;while (j<T0)/计算 next(j)从 next(2)到 next(T0) , T0是 T 的长度但并不意味着只循环m-1次，因为在循环体中j的值可能不发生变化if (k=0|Tj=Tk)/没有重叠真子串和(有重叠真子串但 Tj=Tk)时都应该得出next(j+1

26、)的值next+j=+k;/ 书上：(+j ; +k; nextj=k;else k=next(k);/否则，得不出next(j+1)的值，所以j不变，k退回到next(k),重复匹 配。/end of get_next不加注看起来更简洁一些：void get_next(sstring T, int &next)(j=1; k=nextj=0;while (j<T0)if (k=0|Tj=Tk)next+j=+k;else k=next(k);/end of get_next仍以模式串a b a a b c a c为例，验证一下该算法。 next1=0(2) j=1 ； k=0;

27、满足 k=0;所以 j=2;k=1; next2=1j=2 ； k=1;不满足 k=0 也不满足 T2=T1;所以 k=nextk=next1=0j=2 ; k=0;满足 k=0;所以 j=3;k=1; next3=1(4) j=3 ; k=1;满足 T3=T1;所以 j=4;k=2; next4=2(5) j=4;k=2;不满足 k=0 也不满足 T4=T2;所以 k=nextk=next2=1j=4;k=1;满足 t4=T1;所以 j=5;k=2; next5=2 j=5;k=2;满足 T5=T2;所以 j=6;k=3; next6=3 j=6;k=3;不满足 k=0 也不满足 T6=T3

28、;所以 k=nextk=next3=1j=6;k=1;不满足 k=0 也不满足 T6=T1;所以 k=nextk=next1=0j=6;k=0;满足 k=0;所以 j=7;k=1; next7=1(8) j=7;k=1;满足 T7=T1;所以 j=8;k=2; next8=2si+1起和模式重新开始匹配。第一趟主串模式产acabaabaabcacabaabcac| j=2 next2=la ab c第二趟主串模式广2acabaabaabcaca ab c第三趟主串模式af j=l next11= 0尸=8acabaabaabcacabaabcaca ab cnext值表sj12345678模式

29、ab3.abcacnextjj01131利用next值表进行匹配的过程：假设以i和j分别指示主串和模式串中正待比较的字符，若 si=tj，则i和j分别增1,否则，i 不变，而j退回到nextj的位置再比较，若j退回到值为0 （即模式的第一个字符失配），则 将模式继续向右滑动一个位置，即从主串的下一个字符f j=6 next 6=3第四趟主串模式卜* » |i-I4 acabaabaabcac a ab c abaabcacf j二3 *KMP算法：int index_KMP(sstring s, sstring t, int pos)(利用模式串的next函数求t在主串s中第pos个

30、字符之后的位置的KMP算法,/t 非空，1<=pos<=strlength(s)i=pos; j=1;while(i<=s0&&j<=t0)(if (j=0|si=tj)+i;+j;else j=nextj;if (j>t0) return i-t0;else return 0;/index_kmpnext函数修正算法：例：目标串="aaabaaaab ' w模式串=bh aaaab 其next 值为«J1 2 3 4 5模式a a a a bnextQ0 12 3 4匹配过程如下：第翅主串 aaabaaaab模式 a

31、a a a b| next4=3第副 主串 aaabaaaab模式 a a a a b| next3=2第三通主串模式aaabaaaaba a a a b| next 2 =1第四趟主串 aa往baaaab模式 aa a abA next l=0第五趟主串 aaabaaaab模式a a a ab从以上的匹配过程可以看出next函数在某些情况下，还可以改进。模式中味着si与t4不匹配时，si要与tnext4即t3匹配，而实际上又存在时 t3 易见si与t3也不匹配，t2 , t1也同样。next4=3,意t4,显而所以next函数可以做这样的改进：在原 next基础上，若 tj=tk , k=n

32、extk,直到 tj<>tk。在程序中可以不用循环，因为在计算前面的nextval时已经做了修正，只需作nextvalj= nextvalk即可。void get_nextval(sstring T, int &nextval)(求模式串T的next函数修正值并存入数组nextval。j =1; k= nextvalj =0;while (j<T0)/计算 next(j)从 next(2)到 next(T0),if (k=0|Tj=Tk)/没有重叠真子串和(有重叠真子串但Tj=Tk)时都能够得出结论( +j;+k;if (Tj!=Tk) nextvalj=k;/ 这时

33、的 Tj事实上是 Tj+1 , Tk事实上是 Tk+1 else nextvalj= nextvalk;else k=next(k);/ 否则，j 不变，k 退回到 next(k)。/end用此函数计算模式"aaaab”的nextval值。(1) nextval1=0(2) j=1,k=0 j=2,k=1,! (Tj!=Tk) nextval2= nextval1=0(3) j=2,k=1, Tj=Tkj=3,k=2,! (Tj!=Tk)nextval3=nextval2=0(4) j=3,k=2, Tj=Tkj=4,k=3,! (Tj!=Tk)nextval4=nextval3=0

34、(5) j=4,k=3, Tj=Tkj=5,k=4,(Tj!=Tk)nextval5=4模式aaaabnextj0 12 3 4改进后的匹配过程:aaabaaaab aaaabnext4 = 0第一趟主串 aaabaaaab'模式aaaabI例题分析1. 设正文长度为n,模式串长度为 m,KMP算法的时间复杂度为多少？O(n+m)因为尽管从算法上分析最坏的时间复杂度是O(n*m),但在一般情况下，其实际的执行时间近似于O(n+m),因此至今仍被采用。当目标串为“0000,0000,0000,0000,00001 ”，模式串为“ 0001 ”，此视为最坏情况。2. 设s为一个长度为n的串

35、，其中的字符各不相同， 则s中的互异的非平凡子串(非空 且不同于s本身)的个数是多少？1个字符的子串有n个，两个字符的子串有 n-1个，.n-1个字符的子串有2个。非平凡子串的个数=n+(n-1)+(n-2)+.+3+2=(n(n+1)/2-13.设目标为 s="abcaabbabcabaacbacbia，模式 p="abcabaef。(1) 计算模式p的next函数值。(2) 不写出算法，只画出利用 KMP算法(采用next函数值)进行模式匹配时的每一 趟的匹配过程。(1)模式串next1 2 3 4 5 6 7 a b c a b a a 0 1 1 1 2 3 2第趟a b c a a b b a b c a b a a c b a c b a a b c a bi=5j=5 失