Cod sursa(job #2796021)

Utilizator Mihai.MocanuMihai mmm Mihai.Mocanu Data 7 noiembrie 2021 14:01:53
Problema Potrivirea sirurilor Scor 14
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.33 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];
long long power[2];
long long mainHash[2];
long long curentHash[2];
long long Rez[1000];

long long Citire(long long x){
  long long 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;
}

long long PowLog(long long nr,long long n,long long 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;
}

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

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

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


int main(){
  long long 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,"%lld\n",r);

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


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