Pagini recente » Cod sursa (job #1217858) | Cod sursa (job #2564146) | Cod sursa (job #2238364) | Cod sursa (job #2684455) | Cod sursa (job #1516030)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000001
#define MOD1 1000000007
#define MOD2 1000000021
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, put1, put2, nr1, nr2, clar1, clar2, a, b, cop1, cop2;
char c;
c=fgetc(fin);
n1=0;
clar1=0;
while(c!='\n'){
n1++;
v1[n1]=c;
c=fgetc(fin);
}
c=fgetc(fin);
n2=0;
while(c!='\n' && c!=EOF){
n2++;
v2[n2]=c;
c=fgetc(fin);
}
baza1=1;
for(i=1; i<n1; i++){
baza1*=123;
baza1%=MOD1;
}
baza2=1;
for(i=1; i<n1; i++){
baza2*=123;
baza2%=MOD2;
}
// printf("%lld %lld", baza1, baza2);
clar1=0;
clar2=0;
put1=1;
put2=1;
for(i=n1; i>=1; i--){
clar1=(clar1+v1[i]*put1)%MOD1;
clar2=(clar2+v1[i]*put2)%MOD2;
put1*=123;
put2*=123;
put1%=MOD1;
put2%=MOD2;
}
// printf("%lld %lld\n", clar1, clar2);
nr1=0;
nr2=0;
put1=1;
put2=1;
for(i=n1; i>=1; i--){
nr1=(nr1+v2[i]*put1)%MOD1;
nr2=(nr2+v2[i]*put2)%MOD2;
put1=(put1*123)%MOD1;
put2=(put2*123)%MOD2;
}
// printf("%lld %lld\n", nr1, nr2);
// printf("%lld", clar1);
solutii=0;
if(clar1==nr1 && clar2==nr2){
solutii++;
sol[solutii]=0;
}
for(i=2; i<=n2-n1+1; i++){
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){
if(solutii<1000){
solutii++;
sol[solutii]=i-1;
}
}
// printf("%d %lld %lld %lld %lld %lld %lld %lld\n", i, a, nr1, clar1, nr2, clar2, baza1, baza2);
}
fprintf(fout, "%d\n", solutii);
for(i=1; i<=solutii; i++)
fprintf(fout, "%d ", sol[i]);
return 0;
}