Pagini recente » Cod sursa (job #1110445) | Cod sursa (job #243569) | Cod sursa (job #3262783) | Cod sursa (job #2010577) | Cod sursa (job #2034814)
#include <cstdio>
#include <cstring>
using namespace std;
int MOD1=666013;
int MOD2=666019;
char s[2000005];
char w[2000005];
int sol[2000005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int nrsol=0,lw,ls;
scanf("%s%s",&w,&s);
lw=strlen(w);
ls=strlen(s);
int rez1=0,rez2=0;
for(int i=0;i<lw;++i)
{
rez1=(rez1*27+w[i]-'A'+1)%MOD1;
rez2=(rez2*27+w[i]-'A'+1)%MOD2;
}
int r1=0,r2=0;
for(int i=0;i<lw;++i)
{
r1=(r1*27+s[i]-'A'+1)%MOD1;
r2=(r2*27+s[i]-'A'+1)%MOD2;
}
if(r1==rez1&&r2==rez2)
{
sol[++nrsol]=0;
}
int p1=1,p2=1;
for(int i=1;i<lw;++i){
p1=p1*27%MOD1;
p2=p2*27%MOD2;
}
for(int i=lw;i<ls;++i)
{
r1-=(s[i-lw]-'A'+1)*p1;
r2-=(s[i-lw]-'A'+1)*p2;
if(r1<0)
r1+=MOD1;
if(r2<0)
r2+=MOD2;
r1=(r1*27+s[i]-'A'+1)%MOD1;
r2=(r2*27+s[i]-'A'+1)%MOD2;
if(r1==rez1&&r2==rez2)
{
sol[++nrsol]=i-lw+1;
}
}
printf("%d\n",nrsol);
for(int i=1;i<=nrsol;++i)
printf("%d ",sol[i]);
return 0;
}