Pagini recente » Cod sursa (job #1095152) | Cod sursa (job #795665) | Cod sursa (job #775996) | Cod sursa (job #450727) | Cod sursa (job #1516896)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000001
#define MOD1 1000007
#define MOD2 1000021
char v1[MAXN], v2[MAXN];
int sol[MAXN];
int main(){
FILE*fin=fopen("strmatch.in", "r");
FILE*fout=fopen("strmatch.out", "w");
int n1, n2, i, solutii;
int baza1, baza2, nr1, nr2, clar1, clar2, a, b, cop1, cop2;
char c;
c=fgetc(fin);
n1=0;
clar1=0; clar2=0;
baza1=1; baza2=1;
while(c!='\n'){
n1++;
v1[n1]=c;
clar1=(clar1*123+v1[n1])%MOD1;
clar2=(clar2*123+v1[n1])%MOD2;
cop1=baza1;
cop2=baza2;
baza1=(baza1*123)%MOD1;
baza2=(baza2*123)%MOD2;
c=fgetc(fin);
}
baza1=cop1; baza2=cop2;
c=fgetc(fin);
n2=0;
while(c!='\n' && c!=EOF){
n2++;
v2[n2]=c;
c=fgetc(fin);
}
nr1=0; nr2=0;
for(i=1; i<=n1; i++){
nr1=(nr1*123+v2[i])%MOD1;
nr2=(nr2*123+v2[i])%MOD2;
}
// printf("%lld %lld\n", nr1, nr2);
// printf("%lld", clar1);
solutii=0;
if(clar1==nr1 && clar2==nr2){
solutii++;
sol[solutii]=0;
}
i=2;
while(i<=n2-n1+1){
// nr1=(((nr1-(v2[i-1]*baza1)%MOD1+MOD1)*123)%MOD1+v2[i+n1-1])%MOD1;
// nr2=(((nr2-(v2[i-1]*baza2)%MOD2+MOD2)*123)%MOD2+v2[i+n1-1])%MOD2;
nr1=((nr1-(v2[i-1]*baza1)%MOD1+MOD1)*123+v2[i+n1-1])%MOD1;
nr2=((nr2-(v2[i-1]*baza2)%MOD2+MOD2)*123+v2[i+n1-1])%MOD2;
if(clar1==nr1 && clar2==nr2){
solutii++;
if(solutii<=1000)
sol[solutii]=i-1;
}
i++;
// printf("%d %lld %lld %lld %lld %lld %lld %lld\n", i, a, nr1, clar1, nr2, clar2, baza1, baza2);
}
fprintf(fout, "%d\n", solutii);
if(solutii>1000)
solutii=1000;
for(i=1; i<=solutii; i++)
fprintf(fout, "%d ", sol[i]);
return 0;
}