Cod sursa(job #2795630)

Utilizator albertaizicAizic Albert albertaizic Data 6 noiembrie 2021 18:36:00
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <string.h>

#define LMAX 2000000
#define MOD 666036
#define BASE 256

int v[1000];

char sir[LMAX + 1];
int lsir;

char subs[LMAX + 1];
int lsubs;

int lgput(int a,int n){
  int p;

  p=1;
  while(n>0){
    if((n&1)==1)
      p=(long long)p*a%MOD;
    a=(long long)a*a%MOD;
    n>>=1;
  }

  return p;
}
bool verificare(char sir[],char subs[]){
  int i;

  i=0;
  while(sir[i] && subs[i] && sir[i]==subs[i])
    i++;

  return subs[i]==0;
}

int hash(char sir[],int l) {
  int h,i;

  i=h=0;
  while(i<l){
    h=(h*BASE+sir[i])%MOD;
    i++;
  }

  return h;
}

int cautare(int lsir,int lsubs){
  int sirh,subsh,pow,i,nr;

  subsh=hash(subs,lsubs);
  sirh=hash(sir,lsubs-1);
  pow=lgput(BASE,lsubs-1);

  i=lsubs;
  nr=0;
  while(i<=lsir){
    sirh=(sirh*BASE+sir[i-1])%MOD;
    if(subsh ==sirh && verificare(sir+i-lsubs,subs)){
      if(nr<1000)
        v[nr]=i-lsubs;
      nr++;
    }
    sirh-=sir[i-lsubs]*pow%MOD;
    if(sirh<0)
      sirh+=MOD;
    i++;
  }

  return nr;
}
int main(){
  int i,nr;
  FILE *fin,*fout;
  fin=fopen("strmatch.in", "r");
  fout=fopen("strmatch.out", "w");

  fgets(subs,sizeof(subs),fin);
  lsubs=strlen(subs);
  if(subs[lsubs-1]=='\n')
    subs[--lsubs]=0;

  fgets(sir,sizeof(sir),fin);
  lsir=strlen(sir);
  if(sir[lsir-1]=='\n')
    sir[--lsir]=0;
  nr=cautare(lsir,lsubs);
  fprintf(fout,"%d\n",nr);
  if(nr>1000)
    nr=1000;
  for(i=0;i<nr;i++)
    fprintf(fout,"%d ",v[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}