转载

理解kmp算法

“KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置.KMP算法是一种线性时间复杂的字符串匹配算法，它是对BF算法（Brute-Force，最基本的字符串匹配算法的）改进。对于给的原始串S和模式串P，需要从字符串S中找到字符串P出现的位置的索引。

BF算法与KMP算法的区别

BF算法的时间复杂度O(S.length * T.length)，空间复杂度O(1)。

KMP算法的时间复杂度O(S.length + T.length)，空间复杂度O(T.length)。

字符串匹配算法必须要回溯。但回溯就影响了效率，回溯是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 KMP算法就是利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。

算法流程事例

1.首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位.

理解kmp算法

2.因为B与A不匹配，搜索词再往后移。

理解kmp算法

3.就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

理解kmp算法

4.接着比较字符串和搜索词的下一个字符，还是相同。

理解kmp算法

5.直到字符串有一个字符，与搜索词对应的字符不相同为止。

理解kmp算法

6.这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

理解kmp算法

7.一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

理解kmp算法

8.怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

理解kmp算法

9.已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

理解kmp算法

10.因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

理解kmp算法

11.因为空格与A不匹配，继续后移一位。

理解kmp算法

12.逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

理解kmp算法

13.逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

理解kmp算法

部分匹配表

下面介绍《部分匹配表》是如何产生的。首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合； "后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

理解kmp算法

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度，其前后缀都是表示完全前后缀，即不包含自身的前缀或者后缀。下面以下图为例详细讲解一下

理解kmp算法

为了方便说明这里把搜索词记为：P={ABCDABD}.

1.P[0]表示“A”，其完全前后缀都是空，所以其部分匹配值为0

2.P[1]表示“AB”，其完全前缀为{空，A}，完全后缀为{B，空}，前后缀中只有空相同，所以AB(即P[1])的匹配值为0

3.P[2]表示“ABC”，其完全前缀为{空，A，AB}，完全后缀为{BC，B，空}，前后缀中只有空相同，所以ABC(即P[2])的匹配值为0

4.P[3]表示“ABCD”，其完全前缀为{空，A，AB，ABC}，完全后缀为{BCD，CD，D，空}，前后缀中只有空相同，所以ABCD(即P[3])的匹配值为0

5.P[4]表示“ABCDA”，其完全前缀为{空，A，AB，ABC，ABCD}，完全后缀为{BCDA，CDA，DA，A，空}，前后缀中都有{A}长度为1，所以ABCDA(即P[4])的匹配值为1

6.P[5]表示“ABCDAB”其完全前缀为{空，A，AB，ABC，ABCD，ABCDA}，完全后缀为{BCDAB，CDAB，DAB，AB，B，空}，前后缀中都有{AB}长度为2 ，所以ABCDAB(即P[5])的匹配值为2

7.P[6]表示“ABCDABD”其完全前缀为{空，A，AB，ABC，ABCD，ABCDA，ABCDAB}，完全后缀为{BCDABD，CDABD，DABD，ABD，BD，D ，空}，前后缀中只有空相同，所以ABCDABD(即P[6])的匹配值为0

说明： P[i]表示能匹配的字符串，部分匹配值计算的是能匹配的字符串对应该的值，例如上面的P[5]表示的是如果匹配了字符串“ABCDAB”，则这个字符串对应的部分匹配值为2，而不是第二个字符B的部分匹配值. 为了方便操作，字符串的部分匹配值都对应到字符串的最后一个字符，这样即方便记录也方便查询

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

体现到图中就是这个样子：

理解kmp算法

这个就是next数组的作用了:返回当前的最长公共前后缀长度，假设为len。因为数组是由0开始的，所以next数组让第len位与主串匹配就是拿最长前缀之后的第1位与失配位重新匹配，避免匹配串从头开始！如下图所示:重新匹配刚才的失配位

理解kmp算法

next数组的求解思路

通过上文完全可以对kmp算法的原理有个清晰的了解，那么下一步就是编程实现了，其中最重要的就是如何根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。我先给出我的代码：


  public static int[] makeNext(String ps) {         int q, k;//q:模版字符串下标；k:最大前后缀长度         char[] p = ps.toCharArray();         int m = p.length;//模版字符串长度         int[] next = new int[m];         next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0         for (q = 1, k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值         {             while (k > 0 && p[q] != p[k]) {//递归的求出P[0]···P[q]的最大的相同的前后缀长度k                 k = next[k - 1];           //关键             }             if (p[q] == p[k])//如果相等，那么最大相同前后缀长度加1             {                 k++;             }             next[q] = k;         }         return next;     }

next函数有多种不同的版本，有第一位从0开始的，也有从-1开始的，这里用next数组的，next数组是以下标0开始的！

现在我着重讲解一下makeNext方法所做的工作，如果觉得不好理解就多举几个例子输出一下数组。

我们先从简单的字符串开始，第一个例子是 ABCDABCE

调用如下代码输出：


 System.out.print( Arrays.toString(makeNext("ABCDABCE")));

输出结果：[0, 0, 0, 0, 1, 2, 3, 0]。

注意第一个ABCD,他们的匹配值都是0. A是字符串开头，因为方法中next[0] = 0;从第二个字符开始循环，所以A的匹配值必然是0 。这时k仍然是0，让q=1，开始执行for循环里面的部分，for循环里面嵌套了一个while循环，while循环后是一个if判断：


      while (k > 0 && p[q] != p[k]) {//递归的求出P[0]···P[q]的最大的相同的前后缀长度k           k = next[k - 1];           //关键       }       if (p[q] == p[k])//如果相等，那么最大相同前后缀长度加1       {           k++;        }

对与第一个'B'字母，由于k=0,不满足while循环条件，那么跳过while，进行if判断，比较P[1]和[0],明显第二位的B和第一位的A不相等，所以k不能执行k++，那现在执行for循环的最后一行next[q] = k;即给next[1]赋值，让next[1]等于0 。按照上面的方法可以判断出，对于前4位ABCD的next值都是0，这里很好理解。

先总结一下目前的思路：当前面字符的前一个字符的对称程度为0的时候，只要将当前字符与子串第一个字符进行比较。这个很好理解啊，前面都是0，说明都不对称了，如果多加了一个字符，要对称的话最多是当前的和第一个对称。比如agcta这个里面t的是0，那么后面的a的对称程度只需要看它是不是等于第一个字符a了。

好了，现在开始比较字符串的第5位：A字母。当执行到while循环时，k=0，不满足条件，执行if判断，此时p[q] == p[k]，因为第5位和第1位都是字母A,执行下面的k++,此时k=1,把k赋值给next[4].

下面再看看下一位：字母B,执行while判断，此时k等于1了，k > 0 满足，但是不满足p[q] != p[k]，因为第2位的B和第6位的B比较之后是相等的，那么执行下面的if语句，k再加1. 对于后面的字母C也是同样分析。

按照这个推理，我们就可以总结一个规律，不仅前面是0，如果前面一个字符的next值是1，那么我们就把当前字符与子串第二个字符进行比较，因为前面的是1，说明前面的字符已经和第一个相等了，如果这个又与第二个相等了，说明对称程度就是2了。有两个字符对称了。比如上面agctag，倒数第二个a的next是1，说明它和第一个a对称了，接着我们就把最后一个g与第二个g比较，又相等，自然对称成都就累加了，就是2了。按照上面的推理，如果一直相等，就一直累加，到这里应该很好理解。

当然不可能会那么顺利让我们一直对称下去，如果遇到下一个不相等了，那么说明不能继承前面的对称性了，这种情况只能说明没有那么多对称了，但是不能说明一点对称性都没有，所以遇到这种情况就要重新来考虑，这个也是难点所在。

为了更好的解释下面的步骤，我们换一个更容易观察的例子：ABCDEFABCHABCDEFABCD。这个字符串的next值是：[0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 4]。我们现在只分析最后一位字母X的next值的算法，前面的值的算法和上面的例子一样或者和下面要分析的算法一样。

观察这个字符串，前9位ABCDEFABC和倒数第二位前面的9位完全相等，到比较第10位的时候，比较的是H和最后一位字母D,发现不相等。那么执行while循环里面的，终于走到while循环里了，之前一直跳过了这里。关键代码就是这句：k = next[k - 1]; 因为这时候k=9，所以现在让 k = next[9-1] = next[8] = 3 ; 然后比较p[q]和 p[k]，这时p[q] 是字符串最后一个字母D, p[k]就是p[3]也是D,判断相等，不执行while，执行下面的if, 执行k++,让最后一位next＝4.

那么为什么要让k = next[k - 1] 呢？看下图：

理解kmp算法

如果蓝色的部分相同，则当前next数组的值为上一个next的值加一，可以继承前面的对称性。如果不相同,那么如果要存在对称性，那么对称程度肯定比前面这个的对称程度小，所以要找个更小的对称。也就是说上面那两段长的绿色块不能使用了。那我们只能在最后一位字母D之前找到一个更小的对称，就是一个更小的绿色块。注意这个小的绿色块可以匹配全部字符串的开头。注意下图的说明：

理解kmp算法

我们先要保证的是第一块绿色块和第四块绿色块相等，也就是第一块和最后一块相等，这个不难理解。又因为之前第一块已经和第三块匹配过，第二块已经和第四块匹配过，那么有第一块＝第三块，第二块＝第四块，而我们需要第一块＝第四块，所以1，2，3，4块绿色必须要完全相等。

在ABCDEFABCHABCDEFABCD中绿色的块就是ABC,我们想要得到绿色块ABC的长度，这个长度就是next[k - 1] ＝ next[8] ＝ 3. 为什么，这个next[k - 1]对应是第二个绿色块的最后一位字母，也就是第9位的字母C,这个字母C的next值就是ABCDEFABC中最长公共前后缀的值：3. 有了这个绿色块的长度k了那么 while条件中的p[k]就是第一个绿色块的最后一位的下一位，我们比较这个字母和整个字符串的最后一位就可以了啊，如果相等则k++,否则按照上面的方法，继续迭代，直到k=0 ；

现在我总结一下while循环所做的工作： 1.已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]； 2.此时比较第k项P[k]与P[q],如图1所示 3.如果P[K]等于P[q]，那么很简单跳出while循环; 4.关键如果不等呢？？？那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀，为什么要求P [0]···P[k-1]的最大相同前后缀呢？？原因在于P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同，看来P[0]···P[k-1]这么长的子串是用不了了，那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···Pj-1，看看它的下一项P[j]是否能和P[q]匹配。如图2所示

理解kmp算法

完整的算法

下面是完整的代码：


 public class Test {     public static void main(String args[]) {         String str = "ABCDEFABCHABCDEFABCD";         String ptr = "ABC";         kmp(str, ptr, makeNext(str));     }     public static int[] makeNext(String ps) {         int q, k;//q:模版字符串下标；k:最大前后缀长度         char[] p = ps.toCharArray();         int m = p.length;//模版字符串长度         int[] next = new int[m];         next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0         for (q = 1, k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值         {             while (k > 0 && p[q] != p[k]) {//递归的求出P[0]···P[q]的最大的相同的前后缀长度k                 k = next[k - 1];           //关键             }             if (p[q] == p[k])//如果相等，那么最大相同前后缀长度加1             {                 k++;             }             next[q] = k;         }         return next;     }     public static void kmp(String original, String find, int next[]) {         int j = 0;         for (int i = 0; i < original.length(); i++) {             while (j > 0 && original.charAt(i) != find.charAt(j))                 j = next[j];             if (original.charAt(i) == find.charAt(j))                 j++;             if (j == find.length()) {                 System.out.println("find at position " + (i - j));                 System.out.println(original.subSequence(i - j + 1, i + 1));                 j = next[j];             }         }     } }