Cod sursa(job #1452295)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 iunie 2015 15:11:59
Problema Potrivirea sirurilor Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#define PRIM 100007LL
#define MOD 666013LL
#define COEF 73LL
#define BAZA 991LL
#define DEAL 1000
#define MAXN 2000000
int nrsol, lim, poz[DEAL];
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, x, D, K, k, y, boss;
    FILE *fin, *fout;
    fin=fopen("strmatch.in", "r");
    fout=fopen("strmatch.out", "w");
    fgets(a, MAXN+3, fin);
    fgets(b, MAXN+3, fin);
    boss=sefu=i=n=0;
    d=D=k=K=1;
    while(a[i]!='\n'){
        sefu=(sefu*COEF+a[i])%PRIM;
        boss=(boss*BAZA+a[i])%MOD;
        D=d;
        d=(d*COEF)%PRIM;
        K=k;
        k=(k*BAZA)%MOD;
        i++;
        n++;
    }
    x=y=0;
    i=0;
    d=1;
    while((i<n)&&(b[i]!='\n')){
        x=(x*COEF+b[i])%PRIM;
        y=(y*BAZA+b[i])%MOD;
        i++;
    }
    if((i==n)&&(x==sefu)&&(y==boss)){
        sol(0);
    }
    while(b[i]!='\n'){
        x=((x-(b[i-n]*D)%PRIM+PRIM)*COEF+b[i])%PRIM;
        y=((y-(b[i-n]*K)%MOD+MOD)*BAZA+b[i])%MOD;
        if((sefu==x)&&(boss==y)){
            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;
}