Cod sursa(job #3355846)

Utilizator NERDVANA_MIHNEA_PURCAREAMihnea Purcarea NERDVANA_MIHNEA_PURCAREA Data 26 mai 2026 20:46:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <stdio.h>

#define D 1
#define MAXLEN 2000000

#define BASE 73
#define MODULO1 1000000019
#define MODULO2 1000000021

#define SIGMA 26

char trans[128];
char a[MAXLEN+1], b[MAXLEN+1];
int pos[MAXLEN];
int n, m;
unsigned long long ahash1, ahash2, powerBase1, powerBase2;

void preGen(){
  int i;

  for(i = 0; i < SIGMA; i++)
    trans[i+'a'] = i;

  for(i = 0; i < SIGMA; i++)
    trans[i + 'A'] = i + SIGMA;

  for(i = 0; i < 10; i++)
    trans[i + '0'] = i + 2*SIGMA;
}

void readSir(){
  FILE *in;
  int i;


  in = fopen("strmatch.in", "r");
  n = 0;
  do{
    a[n++] = fgetc(in);
  }while(a[n-1] != '\n');
  n--;

  m = 0;
  do{
    b[m++] = fgetc(in);
  }while(b[m-1] != '\n' && b[m-1] != EOF);
  m--;
  fclose(in);

  ahash1 = ahash2 = 0;
  powerBase1 = powerBase2 = 1;

  i = 0;
  ahash1 = (ahash1*BASE + trans[(int)a[i]])%MODULO1;
  ahash2 = (ahash2*BASE + trans[(int)a[i]])%MODULO2;
  for(i = 1; i < n; i++){
    powerBase1 = (powerBase1*BASE)%MODULO1;
    powerBase2 = (powerBase2*BASE)%MODULO2;

    ahash1 = (ahash1*BASE + trans[(int)a[i]])%MODULO1;
    ahash2 = (ahash2*BASE + trans[(int)a[i]])%MODULO2;
  }
}

void displayAp(){
  FILE *out;

  unsigned long long windowHash1, windowHash2;
  int i, times;

  windowHash1 = windowHash2 = 0;
  for(i = 0; i < n; i++){
    windowHash1 = (windowHash1 * BASE + trans[(int)b[i]]) % MODULO1;
    windowHash2 = (windowHash2 * BASE + trans[(int)b[i]]) % MODULO2;
  }

  times = 0;
  for(; i < m; i++){
    //printf("%d: %lld %lld %lld %lld\n", i-n, windowHash1, ahash1, windowHash2, ahash2);


    if(windowHash1 == ahash1 && windowHash2 == ahash2){
      pos[times++] = i-n;
    }
    
    windowHash1 = ((windowHash1 + MODULO1 - powerBase1*trans[(int)b[i-n]]%MODULO1)%MODULO1 * BASE + trans[(int)b[i]])%MODULO1;
    windowHash2 = ((windowHash2 + MODULO2 - powerBase2*trans[(int)b[i-n]]%MODULO2)%MODULO2 * BASE + trans[(int)b[i]])%MODULO2;
  }
  //printf("%d: %lld %lld %lld %lld\n", i-n, windowHash1, ahash1, windowHash2, ahash2);
  if(windowHash1 == ahash1 && windowHash2 == ahash2){
    pos[times++] = i-n;
  }

  
  out = fopen("strmatch.out", "w");
  fprintf(out, "%d\n", times);
  for(i = 0; i < (times > 1000 ? 1000 : times); i++)
    fprintf(out, "%d ", pos[i]);
  fprintf(out, "\n");
  fclose(out);
}

int main(){
  preGen();
  readSir();
  displayAp();

  return 0;
}

/*
ABA
CABBCABABAB
*/