首先我们需要了解什么是模式匹配？
子串定位运算又称为模式匹配（Pattern Matching）或串匹配（String Matching）。在串匹配中，一般将主串称为目标串，将子串称为模式串。本篇博客统一用S表示目标串，T表示模式串，将从目标串S中查找模式串T的过程称为模式匹配。
虽然我们的主角是KMP模式匹配算法，但我们还是要先从暴力匹配算法讲起，通过发现暴力匹配算法存在的问题，由此来引出KMP模式匹配算法。
朴素的模式匹配算法
【基本思想】
从目标串S的第一个字符开始和模式串T的第一个字符进行比较，如果相等则进一步比较二者的后继字符，否则从目标串的第二个字符开始再重新与模式串T的第一个字符进行比较，以此类推，直到模式串T与目标串S中的一个子串相等，称为匹配成功，返回T在S中的位置；或者S中不存在值与T相等的子串，称匹配失败，返回-1.此算法也称为BF（Brute-Force）算法。
我们先通过一个简单的例子，来了解一下BF算法是怎么回事。假设有一个目标串S为“ababb”，模式串T为“abb”。由于例子比较简单，我们可以绘制出整个的匹配过程。如下图所示：
可以看到匹配流程完全是按照上面给出的基本思想走下来的，首先从目标串S的第一个字符开始和模式串T的第一个字符进行比较（第一趟），如果相等则进一步比较二者的后继字符（第二趟），否则从目标串的第二个字符开始再重新与模式串T的第一个字符进行比较（第三趟，第四趟）。我们重点来关注一下第三趟，此时，发现S[i] != T[j]，则要从目标串S的第二个字符再重新开始，i回溯到i = i – j + 1。因为i – j表示这一趟的起始匹配位置，i – j + 1则意为从这一趟起始比较位置的下一个位置继续进行比较。同时j要回溯到0，即重新与模式串T的第一个字符进行比较。
【BF算法实现】
/* * BF匹配算法 */public static int violentMatching(String s, String t) {int i = 0;int j = 0;while (i < s.length() && j < t.length()) {if (s.charAt(i) == t.charAt(j)) {i++;j++;} else {//i回溯到这一趟起始匹配位置的下一个位置i = i – j + 1;j = 0;}}//当j==t.length()表示目标串S中的一个子串与模式串T完全匹配if (j == t.length()) {//返回这一趟起始匹配位置，即T在S中的位置return i – j;} else {return -1;}}
BF算法的实现比较简单，思维方式也很直接，比较容易理解。但是我们发现存在这样的问题：
第一趟比较结束后，我们可以发现信息：S[0] =T[0]，第二趟比较结束后，得到信息：S[1] = T[1]，第三趟后得到信息：S[2] != T[2]。接下来我们通过观察模式串T可以发现T[0] !=T[1]。因此可以立即得出结论T[0] != S[1]，所以根本无需进行第四趟的比较。可能由于例子比较简单，无法鲜明的体现出KMP算法的优势，下面我们举一个稍微复杂些的例子来看看：
假设有一个目标串S为“ababcabcacb”，模式串为“abcac”，当比较到到S[2]与T[2]时出现失配
如果是按照BF算法，则下一趟应从S[1]与T[0]进行比较开始。但是通过上一趟的比较我们是可以发现：S[0] = T[0]，S[1] = T[1]，S[2] != T[2]。再观察模式串T自身我们发现T[0] != T[1]，因此可以立即得出结论S[1] != T[0]，所以可以省略它们的比较，直接从S[2]与T[0]进行比较开始：
从图中可以看到，当比较到S[6]和T[4]时，再次出现失配情况。如果继续按照BF算法，显然又会多进行几次不必要的比较。那么又应该从目标串和模式串的哪两个位置开始进行比较呢？
从上图可以看出比较结束时，有如下信息：S[2] = T[0]，S[3] = T[1]，S[4] = T[2]，S[5] = T[3]，S[6] != T[4]。然后我们在观察模式串T，可以得到：
（1）T[0] != T[1]，因此T[0] != S[3]，所以可以省略它们的比较。
（2）T[0] != T[2]，因此T[0] != S[4]，省略它们的比较。
（3）T[0] = T[3]，因此T[0] = S[5]，当相等时继续比较两个串的后继字符，所以从S[6]和T[1]开始进行比较。
可以看到应用此方法，只发生了三次重新匹配，就得到了匹配成功的结论，加快了匹配的执行速度。
上面的例子只是大概描述了方法的思路，但是这种方法到底是什么，到底如何精确的进行描述，以及如何用代码实现呢？下面就来解决这些问题。
KMP模式匹配算法
此算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现的，因此该算法被称为克努斯-莫里斯-普拉特操作，简称为KMP算法。
KMP算法，是不需要对目标串S进行回溯的模式匹配算法。读者可以回顾上面的例子，整个过程中完全没有对目标串S进行回溯，而只是对模式串T进行了回溯。通过前面的分析，我们发现这种匹配算法的关键在于当出现失配情况时，应能够决定将模式串T中的哪一个字符与目标串S的失配字符进行比较。所以呢，那三位前辈就通过研究发现，使用模式串T中的哪一个字符进行比较，仅仅依赖于模式串T本身，与目标串S无关。
这里就要引出KMP算法的关键所在next数组，next数组的作用就是当出现失配情况S[i] != T[j]时，next[j]就指示使用T中的以next[j]为下标的字符与S[i]进行比较（注意在KMP算法中，i是永远不会进行回溯的）。还需要说明的是当next[j] = -1时，就表示T中的任何字符都不与S[i]进行比较，下一轮比较从T[0]与S[i+1]开始进行。由此可见KMP算法在进行模式匹配之前需要先求出关于模式串T各个位置上的next函数值。即next[j]，j = 0,1,2,3,…n-1。
求解next数组
根据next数组的特性，匹配过程中一旦出现S[i] != T[j]，则用T[next[j]]与S[i]继续进行比较，这就相当于将模式串T向右滑行j – next[j]个位置，示意图如下：
如果你曾歌颂黎明，那么也请你拥抱黑夜
