一个古老的模式匹配算法。
优点在于不需要回溯主串指针。
在整个匹配过程中，只需要从头到尾扫描主串一次，方便处理那种大文件。
具体实现方法是对子串进行预处理，求得next数组。
这个数组记录的信息是：如果子串的当前比较位与主串不匹配，那么接下来应该把子串的哪个位与主串的当前位（因为主串指针不回溯 所以主串是继续用当前位进行比较）对齐来继续进行比较。
“当匹配过程中产生失配时，模式串向右滑动可行的距离多远。”
这里假设如下：
- 子串中第1到k-1个字符已经与主串匹配完成
- 目前待匹配的是子串第k个字符与主串第i个字符
则待求的next[j]的含义是：子串第j-k+1个字符到第j-1个字符都与主串完成匹配，且子串第j个字符与主串不匹配的前提下，应该把子串的哪个字符与目前与子串第j个字符不匹配的主串字符对齐进行比较，也就是子串最多能向右滑动多远以进行下一次匹配。
试图用语言描述一下求next值的过程
前提：数组第一个元素的逻辑索引值是1
假设当前要求子串中字符X的next值。
把X的前一个字符Y与【逻辑索引值等于Y的next值】的字符Z比较，有两种可能结果。
- 相同。则X的next值等于Z的逻辑索引值+1（当然也就是Y的next值+1）。
- 不同。则再把Y与【逻辑索引值等于Z的next值】的字符Z1比较。
如果一直比较到字符Z的next值为0，但仍然不能实现Z与Y相同，则X的next值为1。
关于nextval（next函数的修正值）
主要是为了解决 当子串存在连续的相同字符时，假设子串有一字符X位于若干与其相同的字符之后，根据上述求next的过程，这些相同字符的next值依次递增1，则按照kmp算法规则，会在发现X不匹配后滑动若干次。但实际上因为这若干个字符都与X相同，所以只需要直接按照X的next值进行滑动即可。简单来说就是为了实现匹配时的连续滑动。
语言描述求nextval的过程
将字符X与【逻辑索引值等于X的next值】的字符Y比较，有两种可能结果。
- 相同。则X的nextval值等于X的next值。
- 不同。则将X与【逻辑索引值等于Y的next值】的字符Z比较，若X与Z相同，则X的nextval值等于Y的（指的是更新到最新的Y，也就是【next值等于最后找到的那个与X相同的Z的逻辑索引值】的Y）的next值。
如果一直比较到字符Z的next值为0，仍不能实现Z与X相同，则X的nextval值为0。