数据结构 —— 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算法
参考文章: