前言 KMP(Knuth-Morris-Pratt)算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。
字符串匹配问题 所谓字符串匹配，是这样一种问题：“字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串 ；P 称为模式串 。下面的图片展示了一个例子。
Brute-Force 顾名思义，Brute-Force是一个纯暴力算法。说句题外话，我怀疑，“暴力”一词在算法领域表示“穷举、极低效率的实现”，可能就是源于这个英文词。
首先，我们应该如何实现两个字符串 A,B 的比较？所谓字符串比较，就是问“两个字符串是否相等”。最朴素的思想，就是从前往后逐字符比较，一旦遇到不相同的字符，就返回False；如果两个字符串都结束了，仍然没有出现不对应的字符，则返回True。实现如下：
枚举 i = 0, 1, 2 … , len(S)-len(P)
将 S[i : i+len(P)] 与 P 作比较。如果一致，则找到了一个匹配。
现在我们来模拟 Brute-Force 算法，对主串 “AAAAAABC” 和模式串 “AAAB” 做匹配：
这是一个清晰明了的算法，实现也极其简单。下面给出Python和C++的实现：
我们成功实现了 Brute-Force 算法。现在，我们需要对它的时间复杂度做一点讨论。按照惯例，记 $n = |S|$ 为串 S 的长度，$m = |P|$ 为串 P 的长度。
Brute-Force的改进思路 经过刚刚的分析，您已经看到，Brute-Force 慢得像爬一样。它最坏的情况如下图所示：
跳过不可能成功的字符串比较 有些趟字符串比较是有可能会成功的；有些则毫无可能。我们刚刚提到过，优化 Brute-Force 的路线是“尽量减少比较的趟数”，而如果我们跳过那些绝不可能成功的字符串比较，则可以希望复杂度降低到能接受的范围。 那么，哪些字符串比较是不可能成功的？来看一个例子。已知信息如下：
模式串 P = “abcabd”.
和主串从S[0]开始匹配时，在 P[5] 处失配。
next数组 next数组是对于模式串而言的。P 的 next 数组定义为：$next[i]$ 表示 $P[0]$ ~ $P[i]$ 这一个子串，使得 前k个字符 恰等于后k个字符 的最大的k. 特别地，k不能取i+1（因为这个子串一共才 i+1 个字符，自己肯定与自己相等，就没有意义了）。
如果把模式串视为一把标尺，在主串上移动，那么 Brute-Force 就是每次失配之后只右移一位；改进算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。但是该如何确定要移多少位呢？
回忆next数组的性质：$P[0]$ 到 $P[i]$ 这一段子串中，前$next[i]$个字符与后$next[i]$个字符一模一样。既然如此，如果失配在 $P[r]$, 那么$P[0]$~$P[r-1]$这一段里面，前$next[r-1]$个字符恰好和后$next[r-1]$个字符相等——也就是说，我们可以拿长度为 $next[r-1]$ 的那一段前缀，来顶替当前后缀的位置，让匹配继续下去！
利用next数组进行匹配 了解了利用next数组加速字符串匹配的原理，我们接下来代码实现之。分为两个部分：建立next数组、利用next数组进行匹配。 首先是建立next数组。我们暂且用最朴素的做法，以后再回来优化：
快速求next数组 终于来到了我们最后一个问题——如何快速构建next数组。
定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。
next[x] 定义为： P[0]P[x] 这一段字符串，使得k-前缀恰等于k-后缀的最大的k.P[x-1] 中最长的公共前后缀。可惜 A 右边的字符和 B 右边的那个字符不相等，next[x]不能改成 now+1 了。因此，我们应该缩短这个now，把它改成小一点的值，再来试试 P[x] 是否等于 P[now].P[x-1]的now-前缀仍然等于now-后缀”的前提下，让这个新的now尽可能大一点。 P[0]P[x-1] 的公共前后缀，前缀一定落在串A里面、后缀一定落在串B里面。换句话讲：接下来now应该改成：使得 A的k-前缀等于B的k-后缀 的最大的k.
模板代码 最后附上洛谷P3375 【模板】KMP字符串匹配 的Python和Java版代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 public class Kmp { private int [] next; private String pattern; public Kmp (String pattern) { this .pattern=pattern; buildNext(pattern); } private void buildNext (String pattern) { next=new int [pattern.length()]; next[0 ]=0 ; int pos=0 ; int i=1 ; while (i<pattern.length()){ if (pattern.charAt(i)==pattern.charAt(pos)){ pos++; next[i]=pos; i++; }else if (pos!=0 ){ pos=next[pos-1 ]; }else { next[i]=pos; i++; } } } public int search (String word) { int index=-1 ; int j=0 ; for (int i=0 ;i<word.length();i++){ while (j<pattern.length()){ if (word.charAt(i)==pattern.charAt(j)){ j++; i++; }else if (j==0 ){ break ; }else { j=next[j-1 ]; } } if (j==pattern.length()){ return i-pattern.length(); } } return index; } }
KMP算法在jdk中的源码应用 学完了这么牛逼的算法，将复杂度从$O(m*n)$降低到了$O(m+n)$，那么来看一下jdk源码String.indexOf和contains是使用kmp算法吗？
1 2 3 public boolean contains (CharSequence s) { return indexOf(s.toString()) > -1 ; }
contains直接调用indexOf方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 static int indexOf (char [] source, int sourceOffset, int sourceCount, char [] target, int targetOffset, int targetCount, int fromIndex) { if (fromIndex >= sourceCount) { return (targetCount == 0 ? sourceCount : -1 ); } if (fromIndex < 0 ) { fromIndex = 0 ; } if (targetCount == 0 ) { return fromIndex; } char first = target[targetOffset]; int max = sourceOffset + (sourceCount - targetCount); for (int i = sourceOffset + fromIndex; i <= max; i++) { if (source[i] != first) { while (++i <= max && source[i] != first); } if (i <= max) { int j = i + 1 ; int end = j + targetCount - 1 ; for (int k = targetOffset + 1 ; j < end && source[j] == target[k]; j++, k++); if (j == end) { return i - sourceOffset; } } } return -1 ; }
indexOf方法采用的是非常朴素的Brute-Force 暴力算法。
所以，为什么jdk没有采用kmp算法？
这就不清楚了，一种说法是短字符串的比较，开辟空间消耗的资源远远比计算的大，kmp更适用的场景是，固定的pattern，不断去比较新的字符串，复用next数组。
