题目描述
给定一个模式串 $S$,以及一个模板串 $P$,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 $P$ 在模式串 $S$ 中多次作为子串出现。
求出模板串 $P$ 在模式串 $S$ 中所有出现的位置的起始下标。
输入格式
第一行输入整数 $N$,表示字符串 P 的长度。
第二行输入字符串 $P$。
第三行输入整数 $M$,表示字符串 $S$ 的长度。
第四行输入字符串 $S$。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。
数据范围
$1≤N≤105$
$1≤M≤106$
样例
输入样例:
3
aba
5
ababa
输出样例:
0 2
算法
KMP实现
时间复杂度
$O(n)$
参考文献
模式串S和模板串P的匹配过程
求next数组的过程
C++ 代码
#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);
// 需要再看看
// 求next的过程, 即再次求每个点的最长后缀长度
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;
}
// KMP匹配过程
for (int i=1, j=0; i<=m; i++)
{
while(j && S[i] != P[j+1]) j = ne[j]; // 模板串向左移动(当从头开始匹配的时候, j=0, 直接跳出循环)
if (S[i] == P[j+1]) j++; // 继续向后匹配
if (j == n) // 模板串匹配到最后, 匹配成功
{
printf("%d ", i-n);
j = ne[j]; // 模板串重新从头开始
}
}
return 0;
}