Cod sursa(job #2795856)

Utilizator Teodor94Teodor Plop Teodor94 Data 7 noiembrie 2021 02:44:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
// sursa remus

#include <stdio.h>
#include <stdlib.h>
#define MOD1 666013
#define MOD2 1000003
#define MAXL 2000000
#define BASE 256
#define MAXSOL 1000 ///Mie in codeblocks testele alea imi dau bine, este un mister

char p[MAXL],s[MAXL + 5];
int r[MAXSOL];

int main(){
  int i,lp,ls,hp1,hp2,hs1,hs2,nr,ri,p1,p2;
  FILE *fin, *fout;

  fin = fopen("strmatch.in","r");
  i = 0;
  p[i] = fgetc(fin);
  while((p[i] >= 'A' && p[i] <= 'Z') || (p[i] >= 'a' && p[i] <= 'z') || (p[i] >= '0' && p[i] <= '9')){
    i++;
    p[i] = fgetc(fin);
  }
  lp = i;

  i = 0;
  s[i] = fgetc(fin);
  while((s[i] >= 'A' && s[i] <= 'Z' )|| (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= '0' && s[i] <= '9')){
    i++;
    s[i] = fgetc(fin);
  }
  ls = i;
  fclose(fin);

  //printf("%s%s",p,s);

  hp1 = hp2 = 0;
  hs1 = hs2 = 0;
  p1 = p2 = 1;
  for(i = 0; i < lp; i ++){
    hp1 = (hp1 * BASE + p[i]) % MOD1;
    hp2 = (hp2 * BASE + p[i]) % MOD2;

    hs1 = (hs1 * BASE + s[i]) % MOD1;
    hs2 = (hs2 * BASE + s[i]) % MOD2;

    if(i > 0){
      p1 = p1*BASE % MOD1;
      p2 = p2*BASE % MOD2;
    }
  }

  nr = 0;
  ri = 0;
  for(; i < ls; i ++){
    if(hp1 == hs1 && hp2 == hs2){
      nr++;
      if(ri < MAXSOL){
        r[ri] = i - lp;
        ri++;
      }
    }

    hs1 -= p1 * s[i - lp] % MOD1;
    hs2 -= p2 * s[i - lp] % MOD2;

    if(hs1 < 0)
      hs1 += MOD1;
    if(hs2 < 0)
      hs2 += MOD2;

    hs1 = (hs1 * BASE + s[i]) % MOD1;
    hs2 = (hs2 * BASE + s[i]) % MOD2;
  }

//  for(int ii=0;ii<ri;ii++)
//    printf("%d ",r[ii]);
//  printf("\n");

  if(hp1 == hs1 && hp2 == hs2){
    nr++;
    if(ri < MAXSOL){
      r[ri] = i - lp; ///Razbunarea copy-paste-ului
      ri++;
    }
  }

//  for(int ii=0;ii<ri;ii++)
//    printf("%d ",r[ii]);
//  printf("\n");

  fout = fopen("strmatch.out","w");
  fprintf(fout,"%d\n",nr);

  for(i=0;i<ri;i++)
    fprintf(fout,"%d ",r[i]);

  fclose(fout);
  return 0;
}