KMP是一种字符串匹配算法,也可以叫它模式匹配算法。
作用大概是判断一个字符串 \(S \ ,len=n\) 是否是字符串 \(T \ ,len=m\) 的字串,并且找出 \(S\) 在 \(T\) 当中每一次出现的位置。
要使用这个算法必须先知道一个十分重要的思想:\(\text{next}\) 数组。
在跑KMP之前需要对于 \(S\) 处理出这个东西(当然,这个东西会出现在很多字符串题里)。
它是一个类似于 AC 自动机的 \(\text{fail}\) 指针的东西(都是在失配时用来转移)。
但是 \(\text{next}_i\) 是求前缀 \(S[1,i]\) 的最长的 Border (同时为原串前缀和后缀的一个子串)。
AC 自动机的 \(\text{fail}\) 之后会说。
定义:\(\text{next}_{i}=\max\{j\ |\ S[1,j]=S[i-j+1,i] \ , j\le i\}\)
说白了,\(\text{next}_i\) 就是对于 \(S\) 的前缀 \(S[1,i]\) ,能够把这个前缀分成两个完全相等的部分 \(S[1\sim j]\) 和 \(S[i-j+1 \sim i]\) 的最大位置 \(j\)。
如果不存在这样子的 \(j\) ,那么 \(\text{next}_i=0\)。
为了方便叙述,定义这个满足条件 \(S[1,j]=S[i-j+1,i]\) 的 \(j\) 为 \(\text{next}_i\) 的"候选项"。
你可以使用朴素的 \(\text{O}(n^2)\)算法来计算,但是这很明显不够啊,我们还不如不用它,直接暴力匹配 \(S\) 和 \(T\) 得了。
那么这个时候就有一个引理:
若 \(j\) 是 \(\text{next}_i\) 的一个候选项,那么满足 \(j^\prime < j\) 的最大的 \(\text{next}_i\) 的"候选项" \(j^\prime\) 是 \(\text{next}_j\) 。
证明使用反证法+画图即可。
也就是说 \((\text{next}_j,j)\) 这个区间当中的数都不是 \(\text{next}_i\) 的“候选项”。
用它可以对求 \(\text{next}\) 的过程进行优化。
根据它可以发现,对于 \(\text{next}_i\) ,他的所有候选项是 \(\text{next}_i,\text{next}_{\text{next}_i},\text{next}_{\text{next}_{\text{next}_i}}...\)
然后又有一个引理2:
如果 \(j\) 是 \(\text{next}_i\) 的一个“候选项”,那么 \(j-1\) 一定是 \(\text{next}_{i-1}\) 的”候选项“。
因为如果 \(S[1,j]=S[i+j-1,i]\) ,那么肯定会有 \(S[1,j-1]=S[i+(j-1)-1,i]\) 。
(画图即可证明)
那么我们在计算完 \(\text{next}_{i-1}\) 之后,我们让 \(\text{next}_i\) 的所有候选项变成 \(\text{next}_{i-1}-1,\text{next}_{\text{next}_{i-1}}-1,\text{next}_{\text{next}_{\text{next}_{i-1}}}-1...\) 就可以了。
复杂度就变成了线性的。
在有了 \(\text{next}\) 之后,我们完成了对 \(S\) 的自行匹配。
现在还需要做一个类似的过程,让 \(S\) 和 \(T\) 进行匹配。
我们定义 \(f_i=\max\{j \ | \ T[i-j+1,i]=S[1,j] \ ,j \le i\}\)。
如果 \(f_i=n\) 那么就证明,\(S\) 在 \(T\) 中出现了一次,并且它出现在区间 \(T[i-n+1,i]\)。
我们类比上面 \(\text{next}\) 的求法就能求出 \(f\)。
\(\text{next}\) 的求法说通俗点就是:
假设 \(\text{next}_{i-1}\) 已经求出来,那么尝试一直扩展这个 \(j\) ,
如果说下一个位置 \(j+1\) 无法满足 \(S[j+1]=S[i]\) ,那么令 \(j=\text{next}_j\) (失配),直到 \(j=0\) 再停止。
如果说下一个位置是满足要求的,那么令 \(j=j+1\)。
复杂度是 \(\text{O}(n+m)\)。
#include<bits/stdc++.h> using namespace std; const int si=1e6+10; int n,m; string s,t; int Next[si],f[si]; int main(){ Next[1]=0; cin>>s>>t; n=(int)s.size(),m=(int)t.size(); s=' '+s,t=' '+t; for(register int i=2,j=0;i<=n;++i){ while(j>0 && s[i]!=s[j+1]) j=Next[j]; if(s[i]==s[j+1]) ++j; Next[i]=j; }// calc next for(register int i=1,j=0;i<=m;++i){ while(j>0 && (j==n || t[i]!=s[j+1])) j=Next[j]; // 这里把 j==n 放到里面了,有些要你求 Border 的题要提出来写(比如lg3375) if(t[i]==s[j+1]) ++j; f[i]=j; if(f[i]==n){ // S exist in T. } }// calc f }
咕咕咕
《算法竞赛进阶指南》
AC 自动机 - OI Wiki