Cod sursa(job #1692328)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 20 aprilie 2016 18:04:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#define MAXN 2000000
#define B1 991
#define B2 73
#define MOD1 666013
#define MOD2 1007
#define MAXP 1000
char v1[MAXN],v2[MAXN];
int poz[MAXP];
int main(){
    FILE*fi,*fout;
    int i,n,nr1,nr2,m,p3,p4,nr3,nr4,con;
    char a;
    fi=fopen("strmatch.in" ,"r");
    fout=fopen("strmatch.out" ,"w");
    a=fgetc(fi);
    n=0;
    nr1=nr2=0;
    while(a!='\n'){
       v1[n++]=a;
       nr1=(nr1*B1+a)%MOD1;
       nr2=(nr2*B2+a)%MOD2;
       a=fgetc(fi);
    }
    a=fgetc(fi);
    m=0;
    while(a!='\n'){
       v2[m++]=a;
       a=fgetc(fi);
    }
    nr3=nr4=0;
    p3=p4=1;
    for(i=0;i<n;i++){
       nr3=(nr3*B1+v2[i])%MOD1;
       nr4=(nr4*B2+v2[i])%MOD2;
       if(i<n-1){
         p3=(p3*B1)%MOD1;
         p4=(p4*B2)%MOD2;
       }
    }
    con=0;
    for(i=n;i<m;i++){
       if(nr1==nr3&&nr2==nr4){
          if(con<MAXP)
            poz[con]=i-n;
          con++;
       }
       nr3=(((MOD1+nr3-(v2[i-n]*p3)%MOD1)%MOD1)*B1+v2[i])%MOD1;
       nr4=(((MOD2+nr4-(v2[i-n]*p4)%MOD2)%MOD2)*B2+v2[i])%MOD2;
    }
    if(nr1==nr3&&nr2==nr4){
          if(con<MAXP)
            poz[con]=i-n;
          con++;
       }
    fprintf(fout,"%d\n" ,con);
    for(i=0;i<con&&i<MAXP;i++)
       fprintf(fout,"%d " ,poz[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}