[KMP算法]蛮力法求next[]与“省力”法求next[]
KMP算法可用于“串匹配”问题。
用单纯的蛮力法进行串匹配的时候，只是在无脑回溯待匹配串与模式串（详细的不说了）,当然这也是解决“串匹配”问题时最直接的想法
但KMP算法的思想，却省去了待匹配串与模式串的回溯，遇到不匹配的字符，模式串选择的是向后移动（其实效果等同于模式串当前不匹配字符的下标回溯到前面的某个位置），从而缩短了时间复杂度。
KMP算法之所以减少了时间复杂度，关键在于之前对于模式串有效的分析，找到模式串中“隔三差五”出现的相同字符或子串，并将其记录到next[]中，一旦遇到不匹配的字符，则将模式串向后移动到上一次出现相同的字符或字符串的位置。（更详细的解说其他人的博客中有，下面是链接KMP算法）
我这里重点记录一下2种求next[]数组的方法（怕以后自己忘了……）
next[]数组中记录的是模式串中在位置i处相等的前缀与后缀的长度
例如"abcab"，next[0]代表子串"a"，next[1]代表子串"ab"，next[2]代表"abc"，next[3]代表"abca"，next[4]代表"abcab"
a，只有一个字符，不存在前缀与后缀之分，因此next[0] = 0；
ab，前缀{a}，后缀{b}，不存在相等的前后缀，因此next[1] = 0；
abc，前缀{a，ab}，后缀{bc，c}，不存在相等的前后缀，因此next[2] = 0;
abca，前缀{a, ab, abc}，后缀{bca, ca, a}，存在最长相等的前后缀a，长度为1个字符，因此next[3] = 1;
abcab，前缀{a, ab, abc, abca}，后缀{bcab, cab, ab, b}，存在最长相等的前后缀ab，长度为2个字符，因此next[4] = 2;
所以next[]数组中的值分别为{0, 0, 0, 1, 2}
下面来看实际中的例子：
待匹配串 s = "abcacababcab";
模式串 t = "abcab"；
使用KMP算法，当s[4] != t[4]，查找next[]数组对应下标的值，即next[4] = 2，但实际使用中，应该对应的是next[3]的值，即t串应移动到t[1]的位置，t[1]与s[4]再进行比较，也就是说，遇到不匹配的字符，即找当前字符的前一个字符所对应的next值，因此考虑将next[]数组的值整体后移：原来的next[] = {0, 0, 0, 1, 2}，整体后移之后，next[0]少值，因此赋值-1，
现在的next[] = {-1，0, 0, 0, 1}，再使用KMP算法时，便可直接找到对应下标的next值进行移动。
设 模式串为t = "abcac"，长度为n，子串中相等的最长前后缀长度为len，初值为0
一、蛮力法求next[]
next[0] = -1;
对于子串ab，只需判断t[0] == t[1]? 若相等，则 len = 1；不等，len = 0；
对于子串abc，先判断 t[0] == t[1]? 若不相等，该子串的最长前缀与后缀便不相等(因为a != b ，自然ab != bc)；若相等，则证明该子串的最长前缀与后缀有相等的可能性，此时暂定 len = 1；接下来继续判断 t[1] == t[2]?是否相等，若相等，而之前判断t[0]与t[1]也相等，则证明其最长的相等前后缀长度为2，此时len = 2;
对于子串abca，同样也判断 t[0] == t[1]?，若相等，则证明存在其最长的前后缀相等的可能性，若不相等，则继续比较t[0] == t[2]?是否相等……因为对于子串的每一个前缀，必定包含第一个字符，这里是a，因此只要比较每个后缀的第一个字符与模式串的第一个字符，便可知道对应长度的前后缀是否可能相等。若在比较的途中遇到不相等的情况，前缀回溯到第一个字符，而后缀继续比较。对于该子串，开始比较t[0]与t[1]，很明显不相等，则可知前缀abc与后缀bca不相等，便没有继续比较下去的需要(即比较t[1]与t[2]是否相等)；接下来继续比较t[0]与t[2]，即判断前缀ab与后缀ca是否相等，同理，继续向后比较……
对于子串abcab，当比较到t[0]与t[3]时，发现它们相等，此时继续比较t[1]与t[4]，又发现相等，则该子串存在相等的前后缀，长度为2……
Java代码如下：
二、“省力”法求next[]
之所以“省力”，是因为当得知前缀与后缀在某个字符上不相等时，我们不需要将前缀的下标回溯到开始状态
对与串aac，先比较t[0]与t[1]，即比较前缀aa与后缀ac的第一个字符是否相等，若不相等可直接跳过，若相等，则暂定 len = 1；
接下来继续比较t[1]与t[2]是否相等，若相等，len = 2，若不相等，则直接便可以知道aac的前缀aa, ac 与aac的后缀 ac, c 没有一个相等的，重置len = 0;
对于串abab，同理，t[0] != t[1] ，len = 0；t[1] != t[2]，len = 0；接下来比较 t[2] 与 t[len]， 相等，len = 1；继续比较 t[2] 与t[3]，不相等，则比较 t[3] 与 t[len]，因为len = 1，所以也就是比较 t[3] 与 t[1]，相等，len = 2，加入数组。
其实道理就在于，我们是从前缀的“头”与后缀的“头”开始比较的，一旦比较过了，相等或者不相等，其信息全部保存在了 len 中，从而不需要再继续从头比较。对于串abab，i = 0 的循环不需要加入，因为此时指向字符a, 不存在前后缀，当i = 1时，此时提出的子串为ab, 比较的是前缀a 与 后缀b是否相等，不相等，len = 0；当 i = 2 的循环结束后，len = 1，根据此信息可以知道，对于子串abab，必不存在前缀aba与bab相等的情况，如果他们要相等，则len 应该是 2；而此时的len = 1，则说明t[0] != t[1]，而t[2] == t[0]，接下来只要继续比较t[0]的下一个字符就可以了。
JAVA代码如下：
再仔细点说，len在上面的循环中是处于连续状态的，它的值，就可以反映某个前缀和后缀的相等情况。
如"babba"这个串，
第一次循环，提取子串"ba"，此时的前缀为{b}，后缀为{a}，a != b，相等的前后缀长度 len = 0;
第二次循环，提取子串"bab"，此时的前缀为{b, ba}，后缀为{ab, b}，已知 len = 0，便可以知道最长前缀(ba)与最长后缀(ab)不可能相等，于是可直接比较次长前缀的第一个字符(b)与次长后缀的第一个字符(b)，发现相等，len++；由此可知，下一次循环，即提取子串"babb"时，前缀(ba)与后缀(bb)的第一个字符已经比较过了，因此只要比较前缀(ba)与后缀(bb)的第二个字符，即(a)与(b)是否相等，便可判定该下标下的 len 长度；
第三次循环，提取子串"babb"，此时前缀为{b, ba, bab}，后缀为{abb, bb, b}。此时我们无需将最长前缀(bab)与最长后缀(abb)相比较便可知道它们不相等，因为第一次循环的时候就已经比较过了它们的第一个字符——不相等，所以自然它们不会相等，否则 len的值应该为2。
每次下标向后移一位，并进行比较，第一次取两个字符，前后缀各一位字符，其实它们就是后续所有子串的前后缀的第一个字符，把他们比较完了，其实就相当于将后续所有子串中的“最长前后缀”的第一个字符比较完毕了；若相等，则下一次就可以直接比较提取子串中的最长前后缀的第二个字符；若不相等，则以后所有子串的最长前后缀都不可能相等，就不需要再比较了；如果第二个字符不相等，则可直接比较第三长的前后缀的第一个字符，这个第三长的前后缀的第一个字符，同时也是下一次提取出的子串中的某个前后缀的第一个字符，如此循环下去，只需遍历模式串一遍，就可以将需要的next[]数组信息补充完整。