KMP模式匹配
KMP 算法能够在线性时间内判定字符串 \(A\left[1\sim N\right]\) 是否是字符串 \(B\left[ 1 \sim M\right]\) 的字串，并求出字符串 \(A\) 在字符串 \(B\) 中各次出现的位置。
详细来讲，KMP 算法分为两步。
- 对字符串 \(A\) 进行自我匹配求出一个数组 \(next\)，\(next\left[i\right]\) 表示 \(A\) 中以 \(i\) 结尾的非前缀字串与 \(A\) 的前缀能匹配的最大长度。特别地当不存在这样的 \(j\) 时，\(next\left[i\right]\) 为 \(0\)，即：
\(next\left[i\right] = \max\{j\}\)，其中 \(j < i\) 且 \(A\left[i-j+1 \sim i\right] = A\left[1\sim j\right]\) - 对字符串 \(A\) 与 \(B\) 进行匹配求出一个数组 \(f\)，其中 \(f\left[i\right]\) 表示 \(B\) 中以 \(i\) 结尾的字串与 \(A\) 的前缀能匹配的最大长度，即：
\(f\left[i\right] = \max\{j\}\)，其中 \(j\le i\) 且 \(B\left[i-j+1\sim i\right] = A\left[1\sim j\right]\)
整个算法时间复杂度为 \(\mathcal{O}(N + M)\)。
\(next\) 数组的求法
- 初始化 \(next\left[1\right] = j = 0\)，假设 \(next\left[1\sim i-1\right]\) 已求出，求解 \(next\left[i\right]\)。
- 不断尝试扩展匹配长度 \(j\)，如果扩展失败即下一个字符不相等，则令 \(j=next\left[j\right]\)，直至 \(j=0\)，应该重新从头开始匹配。
- 如果扩展成功，匹配长度 \(j\) 就加一，\(next\left[i\right]\) 的值就是 \(j\)。
nxt[1]=0;
for(int i=2,j=0;i<=n;i++){
while(j&&a[i]!=a[j+1])j=nxt[j];
if(a[i]==a[j+1])j++;
nxt[i]=j;
}
\(f\) 数组的求法
与求解 \(next\) 数组基本一致。
for(int i=1,j=0;i<=m;i++){
while(j&&(j==n||b[i]!=a[j+1]))j=nxt[j];
if(b[i]==a[j+1])j++;
f[i]=j;
}