Cod sursa(job #2101588)

Utilizator BrandonChris Luntraru Brandon Data 7 ianuarie 2018 18:28:18
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Mod = 90907;
const int Base = 3;

string text, word;
vector <int> H[Mod];
long long firstExp = 1;


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

  return currHash;
}

bool FindHash(int hash) {
  int modHash = hash % Mod;
  for (int i = 0; i < H[modHash].size(); ++i) {
    if (H[modHash][i] == hash) {
      return true;
    }
  }

  return false;
}

void UpdateRollingHash(int stPos, int edPos, long long &currHash) {
  currHash -= (text[stPos] - 'a') * firstExp;
  while (currHash < 0) {
    currHash += Mod;
  }

  currHash *= Base;
  currHash += text[edPos + 1] - 'a';
}

int main() {
  cin >> text;
  int wordSize = 0;
  while (cin >> word) {
    wordSize = word.size();
    int hash = Hash(word);
    H[hash % Mod].push_back(hash);
    // cout << Hash(word) << ' ';
  }
  // cout << '\n';

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

  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);
  // cout << hash << ' ';
  if (FindHash(hash)) {
    ++ans;
  }

  for (int i = 1; i + wordSize - 1 < text.size(); ++i) {
    UpdateRollingHash(i - 1, i + wordSize - 2, hash);
    // cout << hash << ' ';
    if (FindHash(hash)) {
      ++ans;
    }
  }

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