Pagini recente » Cod sursa (job #3152257) | Cod sursa (job #762991) | Cod sursa (job #1726241) | Cod sursa (job #1633867) | Cod sursa (job #2034833)
#include <cstdio>
#include <cstring>
using namespace std;
int MOD1=666013;
int MOD2=666019;
char s[2000005];
char w[2000005];
int sol[2000005];
int cod[5000];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int nrsol=0,lw,ls;
scanf("%s%s",&w,&s);
for(int i=0;i<26;++i)
{
cod['a'+i]=i+1;
cod['A'+i]=i+26+1;
if(i<=10)
cod['0'+i]=i+26+26+1;
}
lw=strlen(w);
ls=strlen(s);
int rez1=0,rez2=0;
for(int i=0;i<lw;++i)
{
rez1=(rez1*63+cod[w[i]])%MOD1;
rez2=(rez2*63+cod[w[i]])%MOD2;
}
int r1=0,r2=0;
for(int i=0;i<lw;++i)
{
r1=(r1*63+cod[s[i]])%MOD1;
r2=(r2*63+cod[s[i]])%MOD2;
}
if(r1==rez1&&r2==rez2)
{
sol[++nrsol]=0;
}
int p1=1,p2=1;
for(int i=1;i<lw;++i){
p1=p1*63%MOD1;
p2=p2*63%MOD2;
}
for(int i=lw;i<ls;++i)
{
r1-=(cod[s[i-lw]])*p1;
r2-=(cod[s[i-lw]])*p2;
if(r1<0)
r1+=MOD1;
if(r2<0)
r2+=MOD2;
r1=(r1*63+cod[s[i]])%MOD1;
r2=(r2*63+cod[s[i]])%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;
}