Pagini recente » Cod sursa (job #2719922) | Cod sursa (job #1650958) | Cod sursa (job #1439151) | Cod sursa (job #1873077) | Cod sursa (job #1919354)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#define MAXN 2000001
#define BAZA 75
#define MOD1 666013
#define MOD2 666019
char a[MAXN],b[MAXN];
std::vector <int> v;
int main()
{
FILE *fin,*fout;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
fscanf(fin,"%s%s",&a,&b);
int na,nb,nr,ha1,ha2,hb1,hb2,p1,p2;
na=strlen(a);nb=strlen(b);
p1=p2=1;nr=hb1=hb2=ha1=ha2=0;
if(na>nb)
{
fprintf(fout,"0");
goto sf;
}
for(int i=0;i<na;i++)
{
ha1=(ha1*BAZA+a[i]-'0')%MOD1;
ha2=(ha2*BAZA+a[i]-'0')%MOD2;
if(i!=0)
{
p1=(p1*BAZA)%MOD1;
p2=(p2*BAZA)%MOD2;
}
}
for(int i=0;i<na;i++)
{
hb1=(hb1*BAZA+b[i]-'0')%MOD1;
hb2=(hb2*BAZA+b[i]-'0')%MOD2;
}
if(ha1==hb1 && ha2==hb2)
{
nr++;
v.push_back(0);
}
for(int i=na;i<nb;i++)
{
hb1=(((hb1-((b[i-na]-'0')*p1)%MOD1+MOD1)%MOD1)*BAZA+b[i]-'0')%MOD1;
hb2=(((hb2-((b[i-na]-'0')*p2)%MOD2+MOD2)%MOD2)*BAZA+b[i]-'0')%MOD2;
if(ha1==hb1 && ha2==hb2)
{
nr++;
v.push_back(i-na+1);
}
}
fprintf(fout,"%d\n",nr);
nr=std::min(nr,1000);
for(int i=0;i<nr;i++)
fprintf(fout,"%d ",v[i]);
sf:fclose(fin);
fclose(fout);
return 0;
}