目的

• 已知字符串 S 和 T，查找 T 在 S 中的位置。

暴力匹配法

• 1-1、从下标 0 位置开始匹配，S[0]-->T[0]、S[1]-->T[1]、S[2]-->T[2]
  

  KMP_1.jpeg

• 1-2、当 S[i]-->T[j] 失配时，T 相对于 S 向右移动一位再按照步骤1开始匹配，S[1]-->T[0]...
  

  KMP_2_1.jpeg

• 1-3、依此反复，直到匹配成功或者失败...

我们注意到，既然在1-1中已经知道了 S[1] == T[1]，而通过 T 自身就可以知道 T[0] != T[1]，因此即使不进行步骤1-2中 S[1]-->T[0] 的比较我们也知道 S[1] != T[0]。因此这样显然做了很多不必要的操作。

KMP 匹配推导

• 2-1、图1中，匹配到 S[2]-->T[2] 时失配，说明 S[0] == T[0]，且 S[1] == T[1]，即 S[0]...S[i] == T[0]...T[j]。假设有一个串 X 与 T[0]...T[j] 不匹配，那么这个串自然也与 S[0]...S[i] 不匹配。如图3所示。
  

  KMP_3.jpeg

• 2-2、回头看步骤1-2，这里用 T[0]（'A'）与 S[1]（'B'）比较，其实可看做 T[0] 与 T[1] 比较，如果 T[0] 与 T[1] 不匹配，依据 2-1 的推理，那么需要一个已经匹配到的子串 T[0]...T[j]（步骤1-1中的j值为1）的前缀和后缀进行比较的过程（T[0]...T[j-1]与T[1]...T[j]）。
  

  KMP_4.jpeg

• 2-3、"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

• 2-4、图4中的“前缀”有：0，01，012

• 2-5、图4中的“后缀”有：3，23，123

• 2-6、如果“前缀”和“后缀”中没有匹配的，则步骤1-2的“向右移动一位”变成了向右移动：
  

  KMP_5.jpeg

• 2-7、步骤1-1中已经匹配了的长度为2，前后缀匹配最大值为0（前缀只有'A'，后缀只有'B'）。因此步骤1-2可以直接将 T 向右移动 2 位进行匹配。

• 2-8、计算 T 的子串（T[0]、T[0]...T[1]、~、T[0]...T[strlen(T)]）每一个的最大匹配值存储到数组 next 中。

• 2-9、整个匹配过程就可以写作：从头开始匹配、遇到失配的字符就到 next 数组获取当前 T 的下标对应的值 k、根据 k 值决定 T 向后移动多少位然后开始新一轮的匹配...，所以图2-1可修改为图2-2
  

  KMP_2_2.jpeg

next 数组

• 3-1、定义用 k 表示某一子串的前后缀最大匹配值，next 数组依次存放 k 值。

• 3-2、任何一个字符串下标为0时都没有“前缀”和“后缀”，因此所有 next[0] = 0（为了不同的算法计算方便也有取为 -1 的）

• 3-3、假设我们知道了 next[j-1] 的值为 k，可以推断出 T[0]...T[k-1] == T[j-k]...T[j-1]，接下来看 T[k] 和 T[j] 是否相等。
  

  KMP_6.jpeg

• 3-4、从图6可以看出，如果 T[k] == T[j]，next[j] = next[j-1] + 1。如果 T[k] != T[j] 呢？为了更加直观，我们把 T[0]...T[K]移到 T[j-k]...T[j] 的下方：
  

  KMP_7.jpeg

• 3-5、这样确实可以达到目的，但是这种方式有没有似曾相识？没错！这不就是跟上面一样的流程嘛，只是在子串中找子串的子串然后进行匹配。
  

  KMP_8.jpeg

• 3-6、我们知道 k 一定比 j 小，也比 j-1 小，既然 next[j-1] 是已知的，那么 next[k] 也一定已经确认过了。而我们又可以很轻易地推导出图中圈出的三个小串是相互匹配的（这三个小串的长度为 next[k]）。

• 3-7、因此我们这时候可以用 T[next[k]+1] 去和 T[j] 比较，如果相等，则 T[j] = next[k] + 1。如果不相等，则递归执行 3-6、3-4，直到找到 T[j] 相匹配的字符或者直到子串长度为0。