AcWing 831. KMP字符串
原题链接
简单
作者:
泠鸢yousa
,
2021-05-20 22:24:31
,
所有人可见
,
阅读 218
算法理解:
- 模式串S: aabaabaaf
- 模板串P: aabaaf
前置知识
- 前缀:所有带有第一个元素,不带最后一个元素的连续子串(跟前缀和有点像)。a,aa,aab,aaba,aabaa.
- 后缀:所有带有最后一个元素,不带第一个元素的连续子串(跟后缀和有点像)。f,af,aaf,baaf,abaaf.
- 最长公共前后缀:上面的aabaaf的最长公共前后缀即为0.
而aabaa这个串的最长公共前后缀aa,aa为2
其他的可以自行求一下:0 1 0 1 2 0
- 我们所要求的next数组即为模板串P的每段以首个元素为起始的子串的最长公共前后缀
- 插一句,这是一个需要背过的算法,理解什么的第一遍就行了。因为真的没法理解,就是个有记忆的回退,你能怎么理解
助记
- 起点:p,s都是从1开始。next数组从1开始
- 两次匹配:i永不后退 j借助ne[]数组回退 到达0停止
检查一下是否匹配上,是则j++
- 求ne:i从2开始
- 求匹配位置:i从1开始
代码
#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
char p[N], s[M];
int ne[N];
int main() {
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; ++i) {
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; ++i) {
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == n) {
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}