Cod sursa(job #2803261)

Utilizator alextmAlexandru Toma alextm Data 19 noiembrie 2021 18:45:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NHASH1 = 100007;
const int NHASH2 = 100021;
const int BHASH = 63;
const int NMAX = 2000000;

int Adauga(int h, char ch, int base, int MOD) {
  return ((h * base) % MOD + ch) % MOD;
}

int Sterge(int h, char ch, int pow, int MOD) {
  return (h - (ch * pow) % MOD + MOD) % MOD;
}

int lgput(int a, int b, int MOD) {
  int ans = 1;
  while(b != 0) {
    if(b & 1)
      ans = (1LL * ans * a) % MOD;
    a = (1LL * a * a) % MOD;
    b /= 2;
  }
  return ans;
}

int main() {
  int p_hash1, s_hash1, p_hash2, s_hash2;
  string pattern, s;
  fin >> pattern >> s;

  int n = s.size();
  int m = pattern.size();

  int pow1 = lgput(BHASH, m - 1, NHASH1);
  int pow2 = lgput(BHASH, m - 1, NHASH2);

  p_hash1 = s_hash1 = p_hash2 = s_hash2 = 0;
  for(int i = 0; i < m; i++) {
    p_hash1 = Adauga(p_hash1, pattern[i], BHASH, NHASH1);
    s_hash1 = Adauga(s_hash1, s[i], BHASH, NHASH1);

    p_hash2 = Adauga(p_hash2, pattern[i], BHASH, NHASH2);
    s_hash2 = Adauga(s_hash2, s[i], BHASH, NHASH2);
  }

  vector<int> sol;
  if(s_hash1 == p_hash1 && s_hash2 == p_hash2)
    sol.push_back(0);

  for(int i = m; i < n; i++) {
    s_hash1 = Adauga(Sterge(s_hash1, s[i - m], pow1, NHASH1), s[i], BHASH, NHASH1);
    s_hash2 = Adauga(Sterge(s_hash2, s[i - m], pow2, NHASH2), s[i], BHASH, NHASH2);

    if(s_hash1 == p_hash1 && s_hash2 == p_hash2)
      sol.push_back(i - m + 1);
  }

  fout << sol.size() << "\n";
  for(int i = 0; i < sol.size() && i < 1000; i++)
    fout << sol[i] << " ";

  return 0;
}