Cod sursa(job #2919075)

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


using namespace std;

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

int vsol[NSOLMAX + 1];

map <char, int> mpval;

void prec_map() {
  int i;
  char ch;

  i = 0;
  for (ch = 'a'; ch <= 'z'; ch++)
    mpval[ch] = i++;
  for (ch = 'A'; ch <= 'Z'; ch++)
    mpval[ch] = i++;
  for (ch = '0'; ch <= '9'; ch++)
    mpval[ch] = i++;
}

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();

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

    if (i < np - 1) {
      crthash1 = (crthash1 * BASE + mpval[s[i]]) % NHASH1;
      crthash2 = (crthash2 * BASE + mpval[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 + mpval[s[i]]) % NHASH1;
    crthash2 = (crthash2 * BASE + mpval[s[i]]) % NHASH2;

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

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

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