热身

从 bbabbcbbabbe这串字符串中
找出bbabbe

示意图.png

BF算法：

无脑穷举，暴力匹配。其核心思想是匹配串（简称S串）和目标串（简称T串）从第一位开始逐一匹配。当某位匹配失败，则S串整体向右移一位，继续和T串匹配。以此类推。每次匹配失败，则移动一格，继续寻找。这其实是一种穷举法，虽然可以解决问题，但是效率低下。

KMP算法：

可以把它理解为BF的改良版，通过观察S串的自身特点，不再一格一格的移动，而是跳跃移动，避免了BF的很多无效匹配，从而大大提升了效率。既然是跳跃，那就有两个无法回避的问题：
1.每次跳的尽可能多（保证效率）。
2.不能瞎跳的太多，导致错过了匹配（保证正确性）。

所以到底应该怎么跳？

首先，我们来看一看热身的例子，T1=S1，T2=S2，T3=S3，T4=S4，T5=S5，
T6 = c，S6 = e。所以在第六位的时候匹配失败。根据前文的介绍，下面一步我们会对S串向右进行移动。那么移动多少格呢？理论上来说最少移动一格，最多移动五格（因为在第六位失败，极限也就是用S1去和T6比）。
如果移动1格，那就是BF算法，效率太慢（有的时候，确实只能移动一格）。
如果移动5格，会不会存在跳过了匹配项的情况？
所以为了知道到底移动多少，我们需要对S1-S5（bbabb）再做一次匹配。
既然前面5位匹配成功了，那么T串的前五位肯定和S串的前五位相同。所以说S串在这段范围内去匹配T串，相当于自己的头去匹配自己的尾巴，这个匹配成功后形成的错位也就是S串最终跳跃的距离。也就相当于用这个头部的后面一位S3去匹配去匹配失败位T6。

通过上面的分析我们可以看出这个下标位3，就是头部的长度（2）+1
所以我们得出结论当S6匹配失败了，就用S3去匹配T串的失败位，我们把这个3记录到S6下面。以后每当S6匹配失败，我们就用S3去和T串的失败位对齐匹配。如果S串的每一位下面，我们都计算得出一个数值。我们是不是就相当于得到了一个跳跃说明书（next数组，也称K数组）？答案：是的。