Cod sursa(job #2794680)

Utilizator YusyBossFares Yusuf YusyBoss Data 5 noiembrie 2021 11:50:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <map>
#define NHASH 666013 /// numar satanist
#define BHASH 256
#define NMAX 2000000

using namespace std;

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

map<char, int> mpval;

int vsol[NMAX + 1];

static inline int minim(int a, int b) {
  return a < b ? a : b;
}

int lgput(int base, int exp) {
  int sol;

  if (exp == 0)
    return 1;
  sol = lgput(base, exp / 2);
  sol = (sol * sol) % NHASH;
  if (exp % 2 == 1)
    sol = (sol * base) % NHASH;
  return sol;
}

static inline int add_ch(int current_hash, char ch) {
  return (current_hash * BHASH + mpval[ch]) % NHASH;
}

static inline int delete_first_ch(int current_hash, char ch, int pow) {
  return (current_hash - mpval[ch] * pow + NHASH) % NHASH;
}

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

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

  return (i == nb);
}

void prec_mp() {
  char ch;

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

int main() {
  int pow, pattern_hash, current_hash, ns, np, i, nsol;
  string pattern, s;
  cin >> pattern >> s;

  ns = s.size();
  np = pattern.size();
  pow = lgput(BHASH, np);

  prec_mp();

  pattern_hash = 0;
  for (i = 0; i < np; i++)
    pattern_hash = add_ch(pattern_hash, pattern[i]);

  current_hash = nsol = 0;
  for (i = 0; i < ns; i++) {
    current_hash = add_ch(current_hash, s[i]);
    if (i >= np) {
      current_hash = delete_first_ch(current_hash, s[i - np], pow);
      if (current_hash == pattern_hash && strcmp(s, pattern, i - np + 1))
        vsol[nsol++] = i - np + 1;
    }
  }

  cout << nsol << "\n";
  for (i = 0; i < minim(1000, nsol); i++)
    cout << vsol[i] << " ";
  return 0;
}