题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N = 1000010;
int n,m;
char P[N],S[N];
int ne[N];
int main()
{
cin >> n;
scanf("\n");
for(int i = 1;i <= n;i++)
{
scanf("%c",&P[i]);
}
scanf("\n");
cin >> m;
scanf("\n");
for(int i = 1;i <= m;i++)
{
scanf("%c",&S[i]);
}
scanf("\n");
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;
}