Cod sursa(job #1761858)

Utilizator BarbumateiBarbu Matei Barbumatei Data 22 septembrie 2016 23:40:27
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD1 256187
#define MOD2 998273
#define BAZA1 59
#define BAZA2 541
#define MAXN 2000000
char a[MAXN+4], b[MAXN+4];
int nr, afis[1000];
int main(){
  int na, nb, i,
      h1a, h2a, h1b, h2b,
      p1, p2;
  FILE *fin, *fout;
  fin=fopen("strmatch.in", "r");
  fout=fopen("strmatch.out", "w");
  fgets(a, MAXN+3, fin);
  fgets(b, MAXN+3, fin);
  na=strlen(a)-1;
  nb=strlen(b)-1;
  p1=p2=1; h1a=h1b=h2a=h2b=0;
  for(i=0; i<na; i++){
    h1a=(h1a*BAZA1+a[i])%MOD1;
    h2a=(h2a*BAZA2+a[i])%MOD2;
    if(i){
      p1=(p1*BAZA1)%MOD1;
      p2=(p2*BAZA2)%MOD2;
    }
  }
  for(i=0; i<na && b[i]!='\n'; i++){
    h1b=(h1b*BAZA1+b[i])%MOD1;
    h2b=(h2b*BAZA2+b[i])%MOD2;
  }
  if(i==na && h1a==h1b && h2a==h2b)
    afis[nr++]=1;
  while(i<nb){
    h1b=( ( h1b - ( b[i-na]*p1 )%MOD1 + MOD1 )* BAZA1 + b[i] )%MOD1;
    h2b=( ( h2b - ( b[i-na]*p2 )%MOD2 + MOD2 )* BAZA2 + b[i] )%MOD2;
    if(h1a==h1b && h2a==h2b)
      if(nr<1000) afis[nr++]=i-na+1;
    i++;
  }
  fprintf(fout, "%d\n", nr);
  for(i=0; i<nr; i++)
    fprintf(fout, "%d ", afis[i]);
  fprintf(fout, "\n");
  fclose(fin);
  fclose(fout);
    return 0;
}