数据结构 —— KMP算法
简单匹配算法
如果我们要对下面的主串P和模式串P进行匹配
步骤一：i=10，j=6
匹配失败，i 回到上一次匹配的起始位置的下一位，j=0
步骤二：i=5，j=0
由此可见，简单匹配算法存在两个问题
- i 发生了回溯（从 i=10 跳到了 i=5 ）
- 没有利用到前面已匹配到的信息（ABCDAB），增加了计算量
因此，我们提出了KMP算法
KMP 算法
步骤一：当 i=10，j=6 时
已匹配的信息有相同的前后缀（如ABCDAB中，AB同时出现在前缀和后缀中），此时模式串P的前缀AB == 主串S的后缀AB（长度为2，即 next[j]=next[6]=2，PS：假设不存在相同的前后缀，则next[j]=0 ），不需要重复进行比较，那么，我们仅需要对 j 进行修改（相当于模式串P向右移动了 j-next[j]=6-2=4， 令 j=next[j]=2 ）
步骤二：改进后变成了 i=10，j=2
此时
- i 的回溯情况被解决（保持 i=10 ），所以当处理从外设输入的庞大文件，可以边读入，边匹配，确保在发生不匹配（即S[i]！=P[j]时）不需要将之前写回外存的部分再次读入，减少了I/O 操作，提高了效率。
- 利用了已匹配到的信息（ABCDAB），不需要重复计算，降低了算法的时间复杂度。
求 next 数组
上述内容介绍了 KMP 算法的运行过程，那么接下来我们将介绍如何求出 KMP 算法中用到的 next 数组
（1）寻找最长前缀后缀
（2）得到最大长度表
（3）求出 next 数组
next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1
PS：本文中的数组范围是从 0~ length-1，故设 next[0]=-1 作为临界点，有一些文章的数组范围是从 1~ length，故设 next[1]=0（next[0]弃置不用）
KMP算法在某些情况下仍存在缺陷，因此提出了改进的KMP算法，具体可参考 数据结构 —— 改进的KMP算法
参考文章：