Cod sursa(job #2796020)

Utilizator Mihai.MocanuMihai mmm Mihai.Mocanu Data 7 noiembrie 2021 13:58:26
Problema Potrivirea sirurilor Scor 14
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <stdio.h>
#include <stdlib.h>
#define HASH_BASE1 593
#define HASH_BASE2 353
#define HASH_SIZE1 1041529
#define HASH_SIZE2 828523

FILE *fin,*fout;
char Str[2][2000000];
int power[2];
int mainHash[2];
int curentHash[2];
int Rez[1000];

int Citire(int x){
  int n;
  char a;
  n=0;
  a=fgetc(fin);
  while(a!='\n' && a!=-1){
    Str[x][n]=a-'A'+1;
    n++;
    a=fgetc(fin);
  }
  return n;
}

int PowLog(int nr,int n,int Mod){
  int p;

  p=1;
  while(n!=0){
    if(n%2){
      p=(long long)p*nr%Mod;
    }
    nr=(long long)nr*nr%Mod;
    n/=2;
  }

  return p;
}

int AddToHash(int Base,int Size,int Hash,int Nr){
  Hash=((long long)Hash*Base+Nr)%Size;
  return Hash;
}

int RemoveFromHash(int Hash,int Size,int nr,int power){
  Hash=((long long)Hash-nr*power)%Size;

  if(Hash<0){
    Hash+=Size;
  }
  return Hash;
}


int main(){
  int n,m,r,i,aux,x,y;
  fin=fopen("strmatch.in","r");
  fout=fopen("strmatch.out","w");

  n=Citire(0);
  m=Citire(1);
  power[0]=PowLog(HASH_BASE1,n,HASH_SIZE1);
  power[1]=PowLog(HASH_BASE2,n,HASH_SIZE2);
  mainHash[0]=0;
  mainHash[1]=0;

  for(i=0;i<n;i++){
    mainHash[0]=AddToHash(HASH_BASE1,HASH_SIZE1,mainHash[0],Str[0][i]);
    mainHash[1]=AddToHash(HASH_BASE2,HASH_SIZE2,mainHash[1],Str[0][i]);
  }
  curentHash[0]=0;
  curentHash[1]=0;
  for(i=0;i<n;i++){
    curentHash[0]=AddToHash(HASH_BASE1,HASH_SIZE1,curentHash[0],Str[1][i]);
    curentHash[1]=AddToHash(HASH_BASE2,HASH_SIZE2,curentHash[1],Str[1][i]);
  }
  r=0;
  for(i=n;i<m;i++){
    x=curentHash[0];
    y=curentHash[1];
    aux=AddToHash(HASH_BASE1,HASH_SIZE1,x,Str[1][i]);
    curentHash[0]=aux;
    aux=AddToHash(HASH_BASE2,HASH_SIZE2,y,Str[1][i]);
    curentHash[1]=aux;
    x=curentHash[0];
    y=curentHash[1];
    aux=RemoveFromHash(x,HASH_SIZE1,Str[1][i-n],power[0]);
    curentHash[0]=aux;
    aux=RemoveFromHash(y,HASH_SIZE1,Str[1][i-n],power[1]);
    curentHash[1]=aux;
    if(curentHash[0]==mainHash[0] && curentHash[1]==mainHash[1]){
      Rez[r]=i-n;
      r++;
    }
  }

  fprintf(fout,"%d\n",r);

  for(i=0;i<r;i++){
    fprintf(fout,"%d ",Rez[i]+1);
  }


  fclose(fin);
  fclose(fout);
  return 0;
}