Pagini recente » Cod sursa (job #3265194) | Cod sursa (job #333308) | Cod sursa (job #1253918) | Cod sursa (job #2028895) | Cod sursa (job #1516041)
#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;
long long 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;
}
for(i=2; i<=n2-n1+1; i++){
// a=v2[i-1]*baza1; a%=MOD1;
// nr1=nr1-a; nr1=nr1+MOD1; nr1%=MOD1; nr1*=123; nr1%=MOD1; nr1+=v2[i+n1-1]; nr1%=MOD1;
// a=v2[i-1]*baza2; a%=MOD2;
// nr2=nr2-a; nr2=nr2+MOD2; nr2%=MOD2; nr2*=123; nr2%=MOD2; nr2+=v2[i+n1-1]; nr2%=MOD2;
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;
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;
}