数据结构之next数组

ACM算法 root 16℃ 0评论

1.以前学的KMP比较急,其实根本不懂。(重学了一遍,彻底理解)

2.暴力匹配就不多说了,那么有什么办法可以优化呢?那就是向前移动多个位置,但是在移动多个位置的同时,必需满足的是要匹配的字符串必需在前面出现过,而且是从开头,不然你无法判断在移动之后,开头那部分是否相同,这一点应该好想。(其实就是找每个所有字串的前后缀是否相等)

3.next数组保存的就是,如果不匹配就从j=next[j]开始向后匹配(其实就是跳到next[j]这个位置,重新比较)

4.那么怎么构造next数组呢?找i和j记录主串和模式串各自的位置,如果匹配就继续同时向后移,如果不相等,主串的i就需要移回起点,继续寻找前后缀相等的字符串。

转载请注明:zxy » 数据结构之next数组

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址