Cod sursa(job #2794738)

Utilizator YusyBossFares Yusuf YusyBoss Data 5 noiembrie 2021 12:56:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.49 kb
#include <fstream>
#include <vector>
#include <map>
#define NHASH1 666013 /// numar satanist
#define NHASH2 666019 /// inca un numar satanist
#define BHASH 63
#define NMAX 2000000

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

vector <int> vsol;
map<char, int> mpval;

int add_ch(int current_hash, char ch, int base, int MOD) {
  return ((current_hash * base) % MOD + mpval[ch]) % MOD;
}

int del_ch(int current_hash, char ch, int pow, int MOD) {
  return (current_hash - (mpval[ch] * pow) % MOD + MOD) % MOD;
}

void prec_mpval() {
  int cnt = 0;
  char ch;

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

int prec_pow(int base, int exp, int MOD) {
  int i, pow;

  pow = 1;
  for (i = 0; i < exp; i++)
    pow = (pow * base) % MOD;
  return pow;
}

bool strcmp(string& A, int pozsta, int pozdra, string& B) {
  int nb, i;

  nb = B.size();

  if (nb != pozdra - pozsta + 1)
    return 0;

  i = 0;
  while (i < nb && A[i + pozsta] == B[i])
    i++;

  return (i == nb);
}

int main() {
  int pow1, pow2, pattern_hash1, pattern_hash2, current_hash1, current_hash2, ns, np, i, nsol;
  string pattern, s;
  cin >> pattern >> s;

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

  prec_mpval();
  pow1 = prec_pow(BHASH, np - 1, NHASH1);
  pow2 = prec_pow(BHASH, np - 1, NHASH2);

  pattern_hash1 = 0;
  pattern_hash2 = 0;
  current_hash1 = 0;
  current_hash2 = 0;
  for (i = 0; i < np; i++) {
    pattern_hash1 = add_ch(pattern_hash1, pattern[i], BHASH, NHASH1);
    pattern_hash2 = add_ch(pattern_hash2, pattern[i], BHASH, NHASH2);

    current_hash1 = add_ch(current_hash1, s[i], BHASH, NHASH1);
    current_hash2 = add_ch(current_hash2, s[i], BHASH, NHASH2);
  }

  if (current_hash1 == pattern_hash1 && current_hash2 == pattern_hash2 && strcmp(s, 0, np - 1, pattern))
    vsol.push_back(0);

  for (i = np; i < ns; i++) {
    current_hash1 = add_ch(del_ch(current_hash1, s[i - np], pow1, NHASH1), s[i], BHASH, NHASH1);
    current_hash2 = add_ch(del_ch(current_hash2, s[i - np], pow2, NHASH1), s[i], BHASH, NHASH2);

    if (current_hash1 == pattern_hash1 && current_hash2 == pattern_hash2 && strcmp(s, i - np + 1, i, pattern))
      vsol.push_back(i - np + 1);
  }

  cout << vsol.size() << "\n";
  for (i = 0; i < vsol.size() && i < 1000; i++)
    cout << vsol[i] << " ";
  return 0;
}