Chapter4_Kmp算法原理演示

1、KMP算法一、朴素的字符串匹配一、朴素的字符串匹配我们可以写出很容易实现的字符串匹配的算法，从A的起始位置和B的起始位置开始比较，如果匹配不成功则从A原先起始位置的下一位开始和B的起始位置开始比较。如果A和B的字符个数分别是m和n，那么这个算法的效率是O(mn)，虽然大部分情况下不至于m*n次但还是有很多不幸的情况发生。一、朴素的字符串匹配一、朴素的字符串匹配设A=“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab” B=“aaaaaaaab”按照朴素算法，每次比到B的最后一位发现不同又要重新从B的开头和A的下一个字符开始比较。一、朴素的字符串匹配一、朴素的字符串匹配朴素算法

2、中不可避免的存在“回溯”现象，因此降低了算法的效率，下面介绍的是一种最坏情况下O(n)的算法（这里假设 m=n），即传说中的KMP算法。二、算法概述二、算法概述KMP算法是用来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。例如”Today is Tuesday”.中是否包含”day”，在哪些位置包含。这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。二、算法概述二、算法概述假如，A=abababaababacb，B=ababacb，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，Ai-j

3、+ 1.i与B1.j完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以Ai结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验Ai+1和Bj+1的关系。当Ai+1=Bj+1时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。二、算法概述二、算法概述当Ai+1Bj+1，KMP的策略是调整j的位置（减小j值）使得Ai-j+1.i与B1.j保持匹配且新的Bj+1恰好与Ai+1匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。位置。i: 1 2 3 4 5 6 7 8 9

4、10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组Pj，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。Pj

5、应该是所有满足B1.Pj=Bj-Pj+1.j的最大值。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述此时，A7=B5，又出现Ai+1Aj+1的情况，由于P5=3，所以j=3。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10

6、i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述此时，i=7,j=3,依旧Ai+1Aj+1，我们将j的值改为P3=1。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b

7、 a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述依旧Ai+1Aj+1，我们将j的值改为P1=0。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 0 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述i: 1 2 3 4 5 6 7 8

8、 9 10A: a b a b a b a a b a b B: a b a b a c bj: 0 1 2 3 4 5 6 7 8 9 10终于，A8=B1，i变为8，j为1。事实上，有可能j到了0仍然不能满足Ai+1=Bj+1（比如A8=d时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现Ai=B1为止。二、算法概述二、算法概述【算法实现】最后的j:=Pj是为了让程序继续做下去，因为我们有可能找到多处匹配。 这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。 j:=0;

9、 for i:=1 to m do begin while (j0)and(aibj+1) do j:=Pj; if ai=bj+1 then inc(j); if j=n then begin writeln(Found at ,i-n+1); j:=Pj; end; end;二、算法概述二、算法概述在此我们应该注意一个现象，Pi的值既是B串前i个中的最大相同前后缀的个数。B: a b a b a c bP: 0 0 1 2 3 求P数组的值二、算法概述二、算法概述预处理不需要按照P的定义写成O(m2)甚至O(m3)的。我们可以通过P1,P2,.,Pj-1的值来获得Pj的值。对于刚才的B=“

10、ababacb”，假如我们已经求出了P1,P2,P3和P4，看看我们应该怎么求出P5和P6。B: a b a b a c bP: 0 0 1 2求P数组的值由于P4=2，可知B3.4=B1.2，由于B5=B3=a，所以可知P5=33B: a b a b a c b二、算法概述二、算法概述现在求P6。由于P5=3，可知B3.5=B1.3求P数组的值B6B4，没有找到相同的前后缀，那么我们能否退而求其次，看在更小的范围内是否能找到Bi+1=Bj+1的情况。在P5=3的范围内能保证的最大相同前后缀是P3=1，因此我们对齐，再做尝试，仍然不行，直到P6=0B: a b a b a c bP: 0 0

11、1 2 3B: a b a b a c bB: a b a b a c bP: 0 0 1 2 3B: a b a b a c b0二、算法概述二、算法概述怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似：求P数组的值 P1:=0;j:=0; for i:=2 to n do begin while (j0)and(bibj+1) do j:=Pj; if bi=bj+1 then inc(j); Pi:=j; end;三、算法分析三、算法分析为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行

12、次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过

13、程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。四、算法应用四、算法应用 最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每

14、一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 21.前两位必定为0和1。2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行

15、比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 23.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 24.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较

16、，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 25.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2

17、3 1 2 6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。nextval值的求法值的求法例如主串为“aaabaaaab”、 模式串为“aaaab”在计算nextval之前要先弄明白，nextval是为了弥补next函数在某些情况下的缺陷而产生的。例如主串为“aaabaaa

18、ab”、模式串为“aaaab”那么，比较的时候就会发生一些浪费的情况：比较到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以直接从主串的第五位开始与模式串进行比较，而事实上，却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。nextval值的求法值的求法例如主串为“aaabaaaab”、 模式串为“aaaab”求nextval数组值有两种方法，一种是不依赖next数组值直接用观察法求得，一种方法是根据next数组值进行推理，两种方法均可使用，视更喜欢哪种方法而定。nextval值的求法值的求法模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 nextval值 0 1 0 2 1 3 0 21.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为