Cod sursa(job #1451941)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 19 iunie 2015 00:58:01
Problema Potrivirea sirurilor Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.3 kb
//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]-'A'))%PRIM;
        d=(d*COEF)%PRIM;
        i++;
        n++;
    }
    i=0;
    d=1;
    while(b[i]!='\n'){
        x[i]=(x[i-1]+d*(b[i]-'A'))%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]==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;
}