Pagini recente » Cod sursa (job #2568450) | Cod sursa (job #1986522) | Cod sursa (job #2978875) | Cod sursa (job #2978872) | Cod sursa (job #1204212)
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;
char a[N],b[N];
int n,m,pi[N];
int soln,sol[1010];
void R()
{
freopen("strmatch.in","r",stdin);
scanf("%s %s",(a+1),(b+1) );
n=strlen(a+1);
m=strlen(b+1);
}
void Prefix()
{
int ind=0,i;
pi[1]=0;
for(i=2; i<=n; i++)
{
while(ind>0 && a[ind+1]!=a[i] )
ind=pi[ind];
if(a[ind+1]==a[i])
ind++;
pi[i]=ind;
}
}
void KMP()
{
int i,ind=0;
for(i=1; i<=m; i++)
{
while(ind>0 && a[ind+1]!=b[i])
ind=pi[ind];
if(a[ind+1]==b[i])
ind++;
if(ind==n)
{
ind=pi[ind];
soln++;
if(soln<=1000)
sol[soln]=i-n;
}
}
}
int main()
{
R();
Prefix();
KMP();
freopen("strmatch.out","w",stdout);
printf("%d\n",soln);
if(soln>1000) soln=1000;
for(int i=1; i<=soln; i++ )
printf("%d ",sol[i]);
return 0;
}