Cod sursa(job #2920431)

Utilizator EZ4ENCEAleksi Jalli EZ4ENCE Data 24 august 2022 12:18:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
#define NHASH1 100007
#define NHASH2 100021
#define BASE 128
#define NSOLMAX 1000

using namespace std;

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

int vsol[NSOLMAX + 1];

int main() {
  int np, ns, patternhash1, patternhash2, crthash1, crthash2, power1, power2, nsol, i;
  string pattern, s;
  fin >> pattern >> s;

  np = pattern.size();
  ns = s.size();

  patternhash1 = patternhash2 = crthash1 = crthash2 = 0;
  power1 = power2 = 1;
  for (i = 0; i < np; i++) {
    patternhash1 = (patternhash1 * BASE + pattern[i]) % NHASH1;
    patternhash2 = (patternhash2 * BASE + pattern[i]) % NHASH2;

    if (i < np - 1) {
      crthash1 = (crthash1 * BASE + s[i]) % NHASH1;
      crthash2 = (crthash2 * BASE + s[i]) % NHASH2;
    }

    if (i > 0) {
      power1 = (power1 * BASE) % NHASH1;
      power2 = (power2 * BASE) % NHASH2;
    }
  }

  nsol = 0;
  for (i = np - 1; i < ns && nsol < NSOLMAX; i++) {
    crthash1 = (crthash1 * BASE + s[i]) % NHASH1;
    crthash2 = (crthash2 * BASE + s[i]) % NHASH2;

    if (crthash1 = patternhash1 && crthash2 == patternhash2)
      vsol[nsol++] = i - np + 1;

    crthash1 = (crthash1 - (power1 * s[i - np + 1]) % NHASH1 + NHASH1) % NHASH1;
    crthash2 = (crthash2 - (power2 * s[i - np + 1]) % NHASH2 + NHASH2) % NHASH2;
  }

  fout << nsol << "\n";
  for (i = 0; i < nsol; i++)
    fout << vsol[i] << " ";
  return 0;
}