Pagini recente » Cod sursa (job #2003926) | Cod sursa (job #1783353) | Statistici Negrea Malina-Adela (malina97) | Cod sursa (job #949929) | Cod sursa (job #1451946)
//x[i]= numarul in baza COEF format cu cifrele de la 1 la i din B, modulo PRIM
#include <stdio.h>
#define PRIM 666013LL
#define COEF 991LL
#define INVC 622329LL
#define DEAL 1000
#define MAXN 2000000
int nrsol, lim, poz[DEAL], x[MAXN+1], inv[MAXN+1];
char a[MAXN+4], b[MAXN+4];
inline void sol(int x){
nrsol++;
if(nrsol<=DEAL){
lim=nrsol;
poz[lim-1]=x;
}
}
int main(){
int sefu, i, d, n;
FILE *fin, *fout;
fin=fopen("strmatch.in", "r");
fout=fopen("strmatch.out", "w");
fgets(a, MAXN+3, fin);
fgets(b, MAXN+3, fin);
sefu=i=n=0;
d=1;
while(a[i]!='\n'){
sefu=(sefu+d*(a[i]-'\n'))%PRIM;
d=(d*COEF)%PRIM;
i++;
n++;
}
x[0]=(b[0]-'\n')%PRIM;
i=1;
d=COEF;
while(b[i]!='\n'){
x[i]=(x[i-1]+d*(b[i]-'\n'))%PRIM;
d=(d*COEF)%PRIM;
i++;
}
inv[0]=1;
for(i=1; i<=MAXN; i++){
inv[i]=(inv[i-1]*INVC)%PRIM;
}
if(x[n-1]==sefu){
sol(0);
}
i=n;
while(b[i]!='\n'){
if(sefu==((x[i]-x[i-n]+PRIM)*(long long)inv[i-n+1])%PRIM){
sol(i-n+1);
}
i++;
}
fprintf(fout, "%d\n", nrsol);
for(i=0; i<lim; i++){
fprintf(fout, "%d ", poz[i]);
}
fclose(fin);
fclose(fout);
return 0;
}