KMP算法

算法3个月前更新 3153917921
14 0 0

规定

  • 字符串均由 字符型数组 储存,且起点数组为1。
  • a(1)为下标为1的a,a(2)为下标为2的a。

最长公共前后缀?

前缀?后缀?

以原字符串起点为起点的子串(非自身)称为父串的一个前缀

以原字符串终点为终点的字串(非自身)称为父串的一个后缀

如:abcde

其前缀:abcd,abc,ab,a;

其后缀:bcde,cde,de,e;

公共前后缀?最长公共前后缀?

当前缀和后缀相同时,被称为(一对)公共前后缀

长度最长的公共前后缀被称为 最长公共前后缀

如:ababa

公共前后缀有:a,aba;注意,ab,ba并非公共前后缀,只有前缀和后缀大小和字符顺寻都严格相等时才被称为公共前后缀。

其最长公共前后缀为:aba

模式串的next数组

next数组长度 与 模式串长度 相同,next数组中的元素与模式串的字符时一一匹配的。

next数组第i个元素的值为 模式串从1到 i 区域内 最长公共前缀的长度。

KMP算法

如上,模式串str[]为ababaa

next[1]等于模式串str[]从1到1区域内(a),最长公共前后缀,则为0

next[2]等于模式串str[]从1到2区域内(ab),最长公共前后缀,则为0

next[3]等于模式串str[]从1到3区域内(aba),最长公共前后缀,则为1

next[4]等于模式串str[]从1到4区域内(abab),最长公共前后缀,则为2

next[5]等于模式串str[]从1到5区域内(ababa),最长公共前后缀,则为3

next[6]等于模式串str[]从1到6区域内(ababaa),最长公共前后缀,则为1

KMP过程

相比于BF算法,KMP的next数组可以帮助我们实现一次跳跃多个(模式串的)字符。

为什么可以?

next指针的含义

next[i] 表示在模式串从1到i区间内 最长公共前后缀 中 前缀的最后一字符所在的位置。

str[i]的值与str[next[i]]的值是相等的。

因为前后缀是相同的,后缀能匹配上时,将前缀移动后缀的地方,也是可以匹配上的。

© 版权声明

相关文章

暂无评论

暂无评论...