Pagini recente » Cod sursa (job #2308823) | Cod sursa (job #2622781) | Cod sursa (job #1195473) | Borderou de evaluare (job #1577237) | Cod sursa (job #278211)
Cod sursa(job #278211)
#include<stdio.h>
#include<string.h>
char n[2000000],m[2000000];
long N,M;
int pi[2000000],x[1005],c;
void pref()
{ int i,k;
N=strlen(n);
k=0;
pi[1]=0;
for(i=2;i<=N;i++)
{ while(k>0&&n[k+1]!=n[i])
k=pi[k];
if(n[k+1]==n[i])
k+=1;
pi[i]=k;
}
}
void kmp()
{ int q,i;
M=strlen(m);
q=0;
pref();
for(i=1;i<M;i++)
{ while(q>0&&n[q+1]!=m[i])
q=pi[q];
if(n[q+1]==m[i])
q+=1;
if(q==N-1)
{ c++;
if(c<=1000)
x[c]=i-N+1;
}
}
}
int main()
{ freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",n);
scanf("%s",m);
kmp();
printf("%d\n",c);
if(c>1000) c=1000;
for(int i=1;i<=c;i++)
printf("%d ",x[i]);
return 0;
}