Cod sursa(job #1516896)

Utilizator herbertoHerbert Mohanu herberto Data 3 noiembrie 2015 18:20:00
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000001
#define MOD1 1000007
#define MOD2 1000021

char v1[MAXN], v2[MAXN];
int sol[MAXN];
int main(){
  FILE*fin=fopen("strmatch.in", "r");
  FILE*fout=fopen("strmatch.out", "w");
  int n1, n2, i, solutii;
  int baza1, baza2, nr1, nr2, clar1, clar2, a, b, cop1, cop2;
  char c;
  c=fgetc(fin);
  n1=0;
  clar1=0; clar2=0;
  baza1=1; baza2=1;
  while(c!='\n'){
    n1++;
    v1[n1]=c;
    clar1=(clar1*123+v1[n1])%MOD1;
    clar2=(clar2*123+v1[n1])%MOD2;
    cop1=baza1;
    cop2=baza2;
    baza1=(baza1*123)%MOD1;
    baza2=(baza2*123)%MOD2;
    c=fgetc(fin);
  }
  baza1=cop1; baza2=cop2;
  c=fgetc(fin);
  n2=0;
  while(c!='\n' && c!=EOF){
    n2++;
    v2[n2]=c;
    c=fgetc(fin);
  }
  nr1=0; nr2=0;
  for(i=1; i<=n1; i++){
    nr1=(nr1*123+v2[i])%MOD1;
    nr2=(nr2*123+v2[i])%MOD2;
  }
//  printf("%lld %lld\n", nr1, nr2);
//  printf("%lld", clar1);
  solutii=0;
  if(clar1==nr1 && clar2==nr2){
    solutii++;
    sol[solutii]=0;
  }
  i=2;
  while(i<=n2-n1+1){
//    nr1=(((nr1-(v2[i-1]*baza1)%MOD1+MOD1)*123)%MOD1+v2[i+n1-1])%MOD1;
//    nr2=(((nr2-(v2[i-1]*baza2)%MOD2+MOD2)*123)%MOD2+v2[i+n1-1])%MOD2;
    nr1=((nr1-(v2[i-1]*baza1)%MOD1+MOD1)*123+v2[i+n1-1])%MOD1;
    nr2=((nr2-(v2[i-1]*baza2)%MOD2+MOD2)*123+v2[i+n1-1])%MOD2;
    if(clar1==nr1 && clar2==nr2){
      solutii++;
      if(solutii<=1000)
        sol[solutii]=i-1;
    }
    i++;

//    printf("%d %lld %lld %lld %lld %lld %lld %lld\n", i, a, nr1, clar1, nr2, clar2, baza1, baza2);
  }
  fprintf(fout, "%d\n", solutii);
  if(solutii>1000)
    solutii=1000;
  for(i=1; i<=solutii; i++)
    fprintf(fout, "%d ", sol[i]);
  return 0;
}