Cod sursa(job #2842593)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 1 februarie 2022 10:55:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#define BAZA 59
#define NMAX 2000000
#define HASH_CODE_1 666013
#define HASH_CODE_2 1000000007
#define MAXR 1000
#define int long long

using namespace std;

int nrofsol;
int p1, p2;
string sirA;
string sirB;
int sol[MAXR + 1];

signed main(){

  ifstream fin ("strmatch.in");
  ofstream fout ("strmatch.out");

  fin >> sirA; int n = sirA.size();
  fin >> sirB; int m = sirB.size();

  int pattern1, pattern2, hash1, hash2;
  pattern1 = pattern2 = hash1 = hash2 = 0;
  p1 = p2 = 1;

  for (int i = 0; i < n; i++){
    pattern1 = (pattern1 * BAZA + sirA[i]) % HASH_CODE_1;
    pattern2 = (pattern2 * BAZA + sirA[i]) % HASH_CODE_2;

    hash1 = (hash1 * BAZA + sirB[i]) % HASH_CODE_1;
    hash2 = (hash2 * BAZA + sirB[i]) % HASH_CODE_2;

    if (i != 0)
      p1 = (p1 * BAZA) % HASH_CODE_1, p2 = (p2 * BAZA) % HASH_CODE_2;
  }

  int parcurg;
  parcurg = n;
  while (parcurg <= m){
    if (hash1 == pattern1 && hash2 == pattern2)
      if (nrofsol < MAXR)
        sol[nrofsol++] =  parcurg - n;
      else
        nrofsol++;

    hash1 -= (sirB[parcurg - n] * p1) % HASH_CODE_1;

    hash2 -= (sirB[parcurg - n] * p2) % HASH_CODE_2;

    if (hash1 < 0)
      hash1 += HASH_CODE_1;
    if (hash2 < 0)
      hash2 += HASH_CODE_2;

    hash1 = (hash1 * BAZA + sirB[parcurg]) % HASH_CODE_1;
    hash2 = (hash2 * BAZA + sirB[parcurg]) % HASH_CODE_2;

    parcurg++;
  }

  fout << nrofsol << "\n";
  for (int i = 0; i < nrofsol && i < MAXR; i++)
    fout << sol[i] << " ";
  //for (int i = 0; i < m; i++)
  return 0;
}