Pagini recente » Cod sursa (job #2023428) | Cod sursa (job #2857652) | Cod sursa (job #2976005) | Cod sursa (job #1381811) | Cod sursa (job #1692319)
#include <cstdio>
#define MAXN 2000000
#define B1 991
#define B2 73
#define MOD1 367
#define MOD2 9901
#define MAXP 1000
char v1[MAXN],v2[MAXN];
int poz[MAXP];
int main(){
FILE*fi,*fout;
int i,n,nr1,nr2,m,p3,p4,nr3,nr4,con;
char a;
fi=fopen("strmatch.in" ,"r");
fout=fopen("strmatch.out" ,"w");
a=fgetc(fi);
n=0;
nr1=nr2=0;
while(a!='\n'){
v1[n++]=a;
nr1=(nr1*B1+a)%MOD1;
nr2=(nr2*B2+a)%MOD2;
a=fgetc(fi);
}
a=fgetc(fi);
m=0;
while(a!='\n'){
v2[m++]=a;
a=fgetc(fi);
}
nr3=nr4=0;
p3=p4=1;
for(i=0;i<n;i++){
nr3=(nr3*B1+v2[i])%MOD1;
nr4=(nr4*B2+v2[i])%MOD2;
if(i<n-1){
p3=(p3*B1)%MOD1;
p4=(p4*B2)%MOD2;
}
}
con=0;
for(i=n;i<m;i++){
if(nr1==nr3&&nr2==nr4){
if(con<MAXP)
poz[con]=i-n;
con++;
}
nr3=(((MOD1+nr3-(v2[i-n]*p3)%MOD1)%MOD1)*B1+v2[i])%MOD1;
nr4=(((MOD2+nr4-(v2[i-n]*p4)%MOD2)%MOD2)*B2+v2[i])%MOD2;
}
if(nr1==nr3&&nr2==nr4){
if(con<MAXP)
poz[con]=i-n;
con++;
}
fprintf(fout,"%d\n" ,con);
for(i=0;i<con&&i<MAXP;i++)
fprintf(fout,"%d " ,poz[i]);
fclose(fi);
fclose(fout);
return 0;
}