Pagini recente » Cod sursa (job #805212) | Cod sursa (job #2841188) | Cod sursa (job #2011629) | Cod sursa (job #2840040) | Cod sursa (job #896546)
Cod sursa(job #896546)
#include<cstring>
#include<cstdio>
char a[2000013],b[2000013];
int na,nb,i,j,ca,cb,da,db,ea,eb,sol[1001],nsol,p,q,t;
inline int cod(char c)
{
int x;
if('a'<=c && c<='z')x=10+(int)c-(int)'a';
else if('A'<=x && x<='Z')x=10+(int)c-(int)'A'+26;
else x=c-(int)'0';
return x;
}
/*inline bool check(int k)
{
int i;
for(i=0;i<nb;++i)
if(a[i+k]!=b[i])return 0;
return 1;
}*/
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b);nb=strlen(b);
gets(a);na=strlen(a);
if(na<nb){printf("0");return 0;}
ca=cb=da=db=ea=eb=0;
p=q=t=1;
for(i=1;i<nb;++i){p=(p*23)%666013;q=(q*37)%666011;t=(t*19)%666019;}
for(i=0;i<nb;++i)
{
ca=(ca*23+cod(a[i]))%666013;
cb=(cb*23+cod(b[i]))%666013;
da=(da*37+cod(a[i]))%666011;
db=(db*37+cod(b[i]))%666011;
ea=(ea*19+cod(a[i]))%666019;
eb=(eb*19+cod(b[i]))%666019;
}
i=0;
do
{
if(ca==cb && da==db)
/*if(check(i))*/
{
++nsol;
if(nsol<1001)sol[nsol-1]=i;
}
ca=(ca-(p*cod(a[i]))%666013+666013)%666013;
ca=(ca*23+cod(a[i+nb]))%666013;
da=(da-(q*cod(a[i]))%666011+666011)%666011;
da=(da*37+cod(a[i+nb]))%666011;
ea=(ea-(t*cod(a[i]))%666019+666019)%666019;
ea=(ea*19+cod(a[i+nb]))%666019;
++i;
}while(i+nb<=na);
printf("%d\n",nsol);
if(nsol>1000)nsol=1000;
for(i=0;i<nsol;++i)printf("%d ",sol[i]);
return 0;
}