對酒當歌,人生幾何? 譬如朝露,去日苦多

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

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

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

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

标签: none

添加新评论