Cod sursa(job #1452283)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 iunie 2015 14:58:57
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#define PRIM 100007LL
#define COEF 73LL
#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;
    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=D=1;
    while(a[i]!='\n'){
        sefu=(sefu*COEF+a[i])%PRIM;
        D=d;
        d=(d*COEF)%PRIM;
        i++;
        n++;
    }
    x=0;
    i=0;
    d=1;
    while((i<n)&&(b[i]!='\n')){
        x=(x*COEF+b[i])%PRIM;
        i++;
    }
    if((i==n)&&(x==sefu)){
        sol(0);
    }
    while(b[i]!='\n'){
        x=((x-(b[i-n]*D)%PRIM+PRIM)*COEF+b[i])%PRIM;
        if(sefu==x){
            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;
}