Cod sursa(job #2101543)

Utilizator BrandonChris Luntraru Brandon Data 7 ianuarie 2018 17:58:04
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>

using namespace std;

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

const int Mod[] = {105499, 106961};
const int MaxMod = 107000;
const int Base = 73;

string text, word;
int H[2][MaxMod];
long long firstExp[2] = {1, 1};


int Hash(string str, int type) {
  long long currHash = 0;
  for (int i = 0; i < str.size(); ++i) {
    currHash *= Base;
    currHash += str[i] - 'a';
    currHash %= Mod[type];
  }

  return currHash;
}

void UpdateRollingHash(int stPos, int edPos, long long &currHash, int type) {
  currHash -= (text[stPos] - 'a') * firstExp[type];
  currHash += Mod[type];
  currHash %= Mod[type];
  currHash *= Base;
  currHash %= Mod[type];
  currHash += text[edPos + 1] - 'a';
  currHash %= Mod[type];
}

int main() {
  cin >> text;
  int wordSize = 0;
  while (cin >> word) {
    wordSize = word.size();
    H[0][Hash(word, 0)] = true;
    H[1][Hash(word, 1)] = true;

    // cout << Hash(word, 0) << ' ' << Hash(word, 1) << '\n';
  }

  for (int i = 1; i < wordSize; ++i) {
    for(int type = 0; type <= 1; ++type) {
      firstExp[type] *= Base;
      firstExp[type] %= Mod[type];
    }
  }

  if (text.size() < wordSize) {
    cout << 0 << '\n';
    return 0;
  }

  string startStr;
  for (int i = 0; i < wordSize; ++i) {
    startStr.push_back(text[i]);
  }

  int ans = 0;
  long long hash[] = {Hash(startStr, 0), Hash(startStr, 1)};
  // cout << hash[0] << ' ' << hash[1] << '\n';
  if (H[0][hash[0]] and H[1][hash[1]]) {
    ++ans;
  }

  // cout << Hash("bcab", 0) << ' ' << Hash("bcab", 1) << '\n' << "---------------------------\n";

  for (int i = 1; i + wordSize - 1 < text.size(); ++i) {
    UpdateRollingHash(i - 1, i + wordSize - 2, hash[0], 0);
    UpdateRollingHash(i - 1, i + wordSize - 2, hash[1], 1);

    // if (i == 1) {
    //   cout << hash[0] << ' ' << hash[1] << '\n';
    // }
    if (H[0][hash[0]] and H[1][hash[1]]) {
      ++ans;
    }
  }

  cout << ans << '\n';
  return 0;
}