Pagini recente » Statistici Butmalai Dan (dan.butmalai) | Istoria paginii runda/sim13123/clasament | Autentificare | Cod sursa (job #565565) | Cod sursa (job #505718)
Cod sursa(job #505718)
# include <stdio.h>
# include <string.h>
char a[2000010],b[2000100];
int qq[2000010],c[2000010];
int i,j,n,m,t,nr,k;
inline void creare (){
k=0;
qq[1]=0;
for (i=2; i<=m; i++){
while (k>0 && b[k+1]!=b[i])
k=qq[k];
if (b[i]==b[k+1])
k++;
qq[i]=k;
}
}
int main (){
freopen ("strmatch.in ","r",stdin);
freopen ("strmatch.out","w",stdout);
gets(b+1);
gets(a+1);
n=strlen(a+1);
m=strlen(b+1);
creare();
t=0;
for (i=1; i<=n; i++){
while (t>0 && b[t+1]!=a[i])
t=qq[t];
if (b[t+1]==a[i]) t++;
if (t==m){
t=qq[t];
nr++;
if (nr<=1000) c[nr]=i-m;
}
}
printf ("%d\n",nr);
if (nr>1000){
for (i=1; i<=1000; i++)
printf ("%d ",c[i]);
printf ("\n");
}
else{
for (i=1; i<=nr; i++)
printf ("%d ",c[i]);
printf ("\n");
}
return (0);
}