KMP算法学习

2024-01-07 17:24:11

代码随想录-B站视频

KMP :三位学者首字母,用于匹配字符串。

时间消耗:O(m+n)。

文本串:需要在其中查找模式串。

模式串:不匹配时,不会直接从文本串的下一个字符,而是直接跳到当前已经匹配好的串后继续匹配。

前缀表:一个字符串中每个字符的最长相等前后缀。

前缀:包含首字母,不包含尾字母的所有字串。

后缀:包含尾字母,不包含首字母的所有字串。

最长相等前后缀

例子:aabaaf

a:是前缀没有后缀,0;

a : aa的长度是1;

b:aab长度是0;

a:aaba长度是1;

a:aabaa长度是2;

f:abaaf长度是0。

a至此得到前缀表:[0,1,0,1,2,0]。

过程:当f不匹配时,查找表发现,前一个位置对应的最长相等前后缀是2,这就是不相等了需要继续去匹配的字符串的位置,相等于跳到前缀的后面,这里就是继续去匹配b的意思。

next(prefix)数组:就是前缀表,表示遇见冲突后next数组会告诉我们需要回退到哪里。

(直接用前缀表就可以实现KMP算法,但是有的实现会进行一些转变)实现过程中会将前缀表进行减一或者右移一位,效果都是初始位置变为-1,后面整体右移或者减一,相当于变成[-1,0,1,0,1,2]或者[-1,0,-1,0,1,-1]。就像上面的在f发生冲突看的是前一位的前缀表,因此整体右移可以直接实现当前位置的匹配,减一个也是访问前一个位置的前缀表,然后再找的时候将这个1再加回来。

实现循环不变量:遇见冲突看前一位。

next数组:

  1. 定义函数来求next数组,传入next数组,传入模式串
  2. 初始化next数组和函数中各个变量。需要一个指向前缀末尾位的j和指向后缀末尾位置的i,这里的j还代表了包括i在内的最长相等前后缀的长度。j=0;next[0]=0。
  3. 处理前后缀不相同的情况。从i开始进入循环遍历到模式串全部长度,i=1开始,因为i不能和j相等。比较当前的j和i,两者不相等时需要回退(不止一步,while),回退到前一位的前缀表对应的位置(相当于匹配时出现了冲突,j=next[j-1],更仔细地说就是当前已匹配上的字串中(也就是当前已经匹配上的后缀中)可以不用再匹配的长度),回退到0停止( j!=0 and s[i]!=s[j] )。
  4. 处理前后缀相同的情况。s[i]=s[j]时相当于匹配上了,j需要加一,相当于匹配上一个。
  5. 更新next数组的值。最后更新next[i]=j。

文章来源:https://blog.csdn.net/weixin_44079186/article/details/135428498
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。