KMP算法能够避免重复匹配

KMP算法主要是根据子串生成的next数组作为回退的依据它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。

这里讲一下为什么用模式串的最大公共前后缀求解NEXT数组参考B站木子喵NEKO的视频【【neko算法课】KMP算法【7期】】

https://www.bilibili.com/video/BV1234y1y7pm/?share_sourcecopy_webvd_source5fc45b3a16cefaa9c36d42d5626cd9e6

用例子思考时我们可以肉眼看到需要移动的位置是根据B向后移动几个可以最大化的对齐A(在i之前意味着找到i前面文本子串(A)与模式子串(B)中重合的部分。

既然i前面都是重合因为i这里发生了不匹配前面都匹配直白说就是一样的那就不用看文本串了直接看模式串前后是否有重合的部分也就是看模式串的最大公共前后缀。

如果没看懂可以往下看。

kmp整体上分两步

A串中i指针前面第一次循环时AB发生不匹配的位置前用A子串与B子串代称。

当A,B遇到不匹配的字符时j指针回退回退依据是当前不匹配位置前一位最大前后缀的长度

为什么呢通俗的说就是不匹配了看前面有哪些已经最大化的匹配上了不匹配位置前一位的next值代表了B自身前后一致的最大长度根据前面讲的A子串等效B子串也就代表了AB子串前后一致的最大长度也就代表了A子串的后面与B子串的前面一致的最大长度也就是B需要向后移动几个字符而j指针的移动代表着B向后移动也就是j指针要移动到的位置。

如果匹配j加一也就意味着j向后移动一位i向后移动写在了for循环里。

同时每次更新next[i]

最后如果j指向了模式串的末尾说明找到了完整匹配返回匹配的起始下标

如果没找到返回-1

0;//这里需要初始化next数组这里用址传递传参给getNext函数vectorint

next(t.size());getNext(t,next);int

0;for(int

//如果j指向t的最后一位说明前面均匹配成功那么返回的第一个匹配项是当前i位置减去已经匹配的t的长度再加一if(j

t.size())

注修改了一处传参遇到的问题涉及值传递、指针传递与地址传递的比较可以略过。

void

1避免不必要的拷贝调用函数时不用创建next的副本不会导致额外的时间内存开销

2保持函数接口整洁引用传递可以直接修改传入的对象不需要显示的管理内存。

3避免空指针问题指针传递需要检查指针是否为空否则运行错误引用传递无需担心因为引用会绑定到有效的对象。