Pagini recente » Cod sursa (job #1833627) | Cod sursa (job #1193897) | Cod sursa (job #145165) | Cod sursa (job #1478615) | Cod sursa (job #2418794)
#include <cstdio>
#include <cstring>
#define MOD1 666013
#define MOD2 1000003
char a[2000001],b[2000001];
int v[1001];
int main(){
FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");
int nra1=0,nra2=0,nrb1=0,nrb2=0,nr=0,n1,n2,i,b1,b2,exp,prod1,prod2,x1,x2;
fscanf (fin,"%s %s",&a,&b);
n1=strlen(a);
n2=strlen(b);
for (i=0;i<n1;i++){
b1=b2=26;
exp=n1-i-1;
prod1=prod2=1;
while (exp>1){
if (exp%2==1){
exp--;
prod1=prod1*b1%MOD1;
prod2=prod2*b2%MOD2;
}
else{
exp/=2;
b1=b1*b1%MOD1;
b2=b2*b2%MOD2;
}
}
if (exp==1){
prod1=prod1*b1%MOD1;
prod2=prod2*b2%MOD2;
}
nra1=(nra1+((a[i]-'A')*prod1)%MOD1)%MOD1;
nra2=(nra2+((a[i]-'A')*prod2)%MOD2)%MOD2;
nrb1=(nrb1+((b[i]-'A')*prod1)%MOD1)%MOD1;
nrb2=(nrb2+((b[i]-'A')*prod2)%MOD2)%MOD2;
if (i==0){
x1=prod1;
x2=prod2;
}
}
for (i=n1;i<n2;i++){
if (nra1==nrb1 && nra2==nrb2){
nr++;
if (nr<=1000)
v[nr]=i-n1;
}
nrb1=((((nrb1-((b[i-n1]-'A')*x1)%MOD1+MOD1)%MOD1)*26)%MOD1+b[i]-'A')%MOD1;
nrb2=((((nrb2-((b[i-n1]-'A')*x2)%MOD2+MOD2)%MOD2)*26)%MOD2+b[i]-'A')%MOD2;
}
if (nra1==nrb1 && nra2==nrb2){
nr++;
if (nr<=1000)
v[nr]=n2-n1-1;
}
fprintf (fout,"%d\n",nr);
if (nr>1000)
nr=1000;
for (i=1;i<=nr;i++)
fprintf (fout,"%d ",v[i]);
return 0;
}