Pagini recente » Cod sursa (job #1600024) | Cod sursa (job #3168761) | Cod sursa (job #2443538) | Cod sursa (job #143294) | Cod sursa (job #1515103)
#include<cstdio>
#include<cstring>
char v[2000001],v2[2000001];
int p[2000001],s[2000001],sol[1001];
int main ()
{freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int k1,k2,i,x,k,q,kmp;
scanf("%s%s",&v,&v2);
k1=strlen(v);
k2=strlen(v2);
if(k1>k2)
{printf("0");
return 0;
}
for(i=k1;i>=0;i--)
v[i+1]=v[i];
for(i=k2;i>=0;i--)
v2[i+1]=v2[i];
v[0]=v2[0]=0;
kmp=0;
for(i=2;i<=k1;i++)
{if(v[i]==v[kmp+1])
kmp++;
else
{kmp=p[i-1];
while(v[i]!=v[kmp+1]&&kmp!=0)
kmp=p[kmp];
if(p[i]>0||v[i]==v[1])
kmp++;
}
p[i]=kmp;
}
q=0;
kmp=0;
for(i=1;i<=k2;i++)
{if(v2[i]==v[kmp+1])
kmp++;
else
{kmp=s[i-1];
while(v2[i]!=v[kmp+1]&&kmp!=0)
kmp=s[kmp];
if(kmp>0||v2[i]==v[1])
kmp++;
}
s[i]=kmp;
if(s[i]==k1)
{q++;
if(q<=1000)
sol[q]=i-k1;
}
}
printf("%d\n",q);
if(q>1000)
q=1000;
for(i=1;i<=q;i++)
printf("%d ",sol[i]);
return 0;
}