Cod sursa(job #2794666)

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

using namespace std;

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

int vsol[NMAX + 1];

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) {
  if (ch >= 'A' && ch <= 'Z')
    return (current_hash * BHASH + ch - 'A') % NHASH;
  return (current_hash * BHASH + ch - 'a') % NHASH;
}

static inline int delete_first_ch(int current_hash, char ch, int pow) {
  if (ch >= 'A' && ch <= 'Z')
    return (current_hash - (ch - 'A') * pow + NHASH) % NHASH;
  return (current_hash - (ch - 'a') * 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);
}

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


  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 < nsol; i++)
    cout << vsol[i] << " ";
  return 0;
}