Cod sursa(job #1490530)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 23 septembrie 2015 18:55:18
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <stdlib.h>
#define BAZA1 991
#define BAZA2 73
#define MOD1 666013
#define MOD2 100007
#define MAXN 2000000
#define MAXNR 1000
char A[MAXN],B[MAXN];
int poz1[MAXNR];
int main(){
    FILE*fi,*fout;
    int i,n,m,c1,c2,con,nrA1,nrB1,nrA2,nrB2,aux1,aux2;
    fi=fopen("strmatch.in" ,"r");
    fout=fopen("strmatch.out" ,"w");
    m=n=0;
    A[0]=fgetc(fi);
    nrA1=nrA2=0;
    c1=c2=1;
    while(A[n]!='\n'){
        A[++n]=fgetc(fi);
        nrA1=(nrA1*BAZA1+A[n-1])%MOD1;
        nrA2=(nrA2*BAZA2+A[n-1])%MOD2;
        aux1=c1;
        aux2=c2;
        c1=(c1*BAZA1)%MOD1;
        c2=(c2*BAZA2)%MOD2;
    }
    c1=aux1;
    c2=aux2;
    B[0]=fgetc(fi);
    while(B[m]!='\n')
        B[++m]=fgetc(fi);
    nrB1=nrB2=0;
    for(i=0;i<n;i++){
        nrB1=(nrB1*BAZA1+B[i])%MOD1;
        nrB2=(nrB2*BAZA2+B[i])%MOD2;
    }
    con=0;
    if(nrB1==nrA1&&nrB2==nrA2){
       poz1[con]=0;
       con++;
    }
    i=1;
    while(i+n-1<m){
        nrB1=((nrB1-(B[i-1]*c1)%MOD1+MOD1)*BAZA1+B[n+i-1])%MOD1;
        nrB2=((nrB2-(B[i-1]*c2)%MOD2+MOD2)*BAZA2+B[n+i-1])%MOD2;
        if(nrB1==nrA1&&nrB2==nrA2){
            if(con<MAXNR)
                poz1[con]=i;
            con++;
        }
        i++;
    }
    fprintf(fout,"%d\n" ,con);
    for(i=0;i<con&&i<MAXNR;i++)
       fprintf(fout,"%d " ,poz1[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}