Pagini recente » Cod sursa (job #2246933) | Cod sursa (job #1917475) | Cod sursa (job #2413333) | Cod sursa (job #1182591) | Cod sursa (job #2537082)
#include <stdio.h>
#include <string.h>
#define S 72
#define MAX 2000000
#define MOD1 957091
#define MOD2 1000000409
char a[MAX],b[MAX];
long long v[MAX];
int main(){
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
long long n,m,i,am1,am2,bm1,bm2,p1,p2,sol=0;
fscanf(fin,"%s",&a);
fscanf(fin,"%s",&b);
n=strlen(a);
m=strlen(b);
if(n>m)
sol=0;
else{
am1=am2=bm1=bm2=0;
for(i=0; i<n; i++){
am1=(am1*S+a[i])%MOD1;
am2=(am2*S+a[i])%MOD2;
bm1=(bm1*S+b[i])%MOD1;
bm2=(bm2*S+b[i])%MOD2;
}
if(am1==bm1 && am2==bm2)
v[sol++]=0;
p1=p2=1;
for(i=1; i<n; i++){
p1=(p1*S)%MOD1;
p2=(p2*S)%MOD2;
}
for(i=n; i<m; i++){
bm1=((bm1-b[i-n]*p1%MOD1+MOD1)*S+b[i])%MOD1;
bm2=((bm2-b[i-n]*p2%MOD2+MOD2)*S+b[i])%MOD2;
if(am1==bm1 && am2==bm2)
v[sol++]=i-n+1;
}
}
fprintf(fout,"%lld\n",sol);
sol=1000<sol ? 1000:sol;
for(i=0; i<sol; i++)
fprintf(fout,"%lld ",v[i]);
fclose(fin);
fclose(fout);
return 0;
}