Cod sursa(job #3160868)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 25 octombrie 2023 10:32:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>

#define MOD1 666013
#define MOD2 1000003
#define BASE 27
#define MAXL 2000000

using namespace std;

int app[MAXL], dr = 0;
char str[MAXL];

int main(){
  char c;
  int s1, s2, l, i, p1, p2, n;
  FILE *fin, *fout;

  fin = fopen("strmatch.in", "r");
  c = fgetc(fin);
  s1 = 0;
  s2 = 0;
  l = 0;

  while(c != '\n'){
    s1 *= BASE;
    s1 += c - 'A' + 1;
    s1 %= MOD1;

    s2 *= BASE;
    s2 += c - 'A' + 1;
    s2 %= MOD2;
    
    l ++;
    c = fgetc(fin);
  }

  p1 = p2 = 1;
  for(i = 0; i < l - 1; i ++){ // Calculam valoarea celei mai semnificative cifre pentru ambele modulo
    p1 *= BASE;
    p1 %= MOD1;

    p2 *= BASE;
    p2 %= MOD2;
  }

  c = fgetc(fin);
  n = 0;
  while(c != '\n'){
    str[n ++] = c - 'A' + 1;
    c = fgetc(fin);
  }
  fclose(fin);

  // printf("%d: %d %d,  %d %d\n", l, s1, s2, p1, p2);
  
  int x1 = 0, x2 = 0;
  for(i = 0; i < l; i ++){
    x1 *= BASE;
    x1 += str[i]; 
    x1 %= MOD1;

    x2 *= BASE;
    x2 += str[i];
    x2 %= MOD2;
  }
  while(i < n){
    // printf("x1 = %d, x2 = %d\n", x1, x2);
    if(x1 == s2 && x2 == s2)
      app[dr ++] = i - l;

    x1 -= p1 * str[(i - l)];
    while(x1 < 0)
      x1 += MOD1;
    x1 *= BASE;
    x1 += str[i]; 
    x1 %= MOD1;

    x2 -= p2 * str[(i - l)];
    while(x2 < 0)
      x2 += MOD2;
    x2 *= BASE;
    x2 += str[i];
    x2 %= MOD2;

    i ++;
  }
  if(x1 == s2 && x2 == s2)
    app[dr ++] = i - l;

  fout = fopen("strmatch.out", "w");
  fprintf(fout, "%d\n", dr);
  for(i = 0; i < dr; i ++)
    fprintf(fout, "%d ", app[i]);
  fprintf(fout, "\n");
  fclose(fout);

  return 0;
}