Cod sursa(job #2794731)

Utilizator YusyBossFares Yusuf YusyBoss Data 5 noiembrie 2021 12:48:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <fstream>
#include <vector>
#include <map>
#define NHASH 666013 /// 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 pow, pattern_hash, current_hash, ns, np, i, nsol;
  string pattern, s;
  cin >> pattern >> s;

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

  prec_mpval();
  pow = prec_pow(BHASH, np - 1, NHASH);

  pattern_hash = 0;
  current_hash = 0;
  for (i = 0; i < np; i++) {
    pattern_hash = add_ch(pattern_hash, pattern[i], BHASH, NHASH);
    current_hash = add_ch(current_hash, s[i], BHASH, NHASH);
  }

  if (current_hash == pattern_hash && strcmp(s, 0, np - 1, pattern))
    vsol.push_back(0);

  for (i = np; i < ns; i++) {
    current_hash = add_ch(del_ch(current_hash, s[i - np], pow, NHASH), s[i], BHASH, NHASH);
    if (current_hash == pattern_hash && 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;
}