Pagini recente » oji_10_2024 | Cod sursa (job #437098) | Cod sursa (job #2474867) | Cod sursa (job #163543) | Cod sursa (job #1761858)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD1 256187
#define MOD2 998273
#define BAZA1 59
#define BAZA2 541
#define MAXN 2000000
char a[MAXN+4], b[MAXN+4];
int nr, afis[1000];
int main(){
int na, nb, i,
h1a, h2a, h1b, h2b,
p1, p2;
FILE *fin, *fout;
fin=fopen("strmatch.in", "r");
fout=fopen("strmatch.out", "w");
fgets(a, MAXN+3, fin);
fgets(b, MAXN+3, fin);
na=strlen(a)-1;
nb=strlen(b)-1;
p1=p2=1; h1a=h1b=h2a=h2b=0;
for(i=0; i<na; i++){
h1a=(h1a*BAZA1+a[i])%MOD1;
h2a=(h2a*BAZA2+a[i])%MOD2;
if(i){
p1=(p1*BAZA1)%MOD1;
p2=(p2*BAZA2)%MOD2;
}
}
for(i=0; i<na && b[i]!='\n'; i++){
h1b=(h1b*BAZA1+b[i])%MOD1;
h2b=(h2b*BAZA2+b[i])%MOD2;
}
if(i==na && h1a==h1b && h2a==h2b)
afis[nr++]=1;
while(i<nb){
h1b=( ( h1b - ( b[i-na]*p1 )%MOD1 + MOD1 )* BAZA1 + b[i] )%MOD1;
h2b=( ( h2b - ( b[i-na]*p2 )%MOD2 + MOD2 )* BAZA2 + b[i] )%MOD2;
if(h1a==h1b && h2a==h2b)
if(nr<1000) afis[nr++]=i-na+1;
i++;
}
fprintf(fout, "%d\n", nr);
for(i=0; i<nr; i++)
fprintf(fout, "%d ", afis[i]);
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}