给定一个模式串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思路:暴力当发生不匹配情况时,p字符串就回退到起始点
// 而kmp只需要退回下一个可能进行匹配的地方
// 即ne[j] j 是已经匹配到的地方
#include<iostream>
using namespace std;
typedef long long ll;
int n,m;
const ll N=1e6+10;
ll ne[N];
// ne[i]=j则说明P[0,j]=P[i-j+1,i]
char S[N],P[N];
int main()
{
cin>>n>>P+1>>m>>S+1; //从1开始输容易处理
//ne[1]=0,所以从2开始;
for(ll i=2,j=0;i<=n;i++)
{
while(j&&P[i]!=P[j+1])j=ne[j];//退无可退或不相P串后退到可能匹配的地方
if(P[i]==P[j+1])j++;
ne[i]=j;
}
for(ll i=1,j=0;i<=m;i++)
{
while(j&&S[i]!=P[j+1])j=ne[j];//与找ne[]类似;
if(S[i]==P[j+1])j++;
if(j==n) //匹配成功
{
cout<<i-n<<" ";
j=ne[j];
}
}
}