LNIP_Seminar1

#include <iostream>
#include <string>
#include <vector>

const int a = 31;
const int simple = 1000000009;

typedef long long ll;

int my_hash_simple(const std::string& s) {
  if (s.empty()) return 0;
  return s[0];
}

int my_hash(const std::string& s, int d) {
  if (s.empty()) return 0;
  ll result = 0;
  for (char c : s) {
    result = (result * a % d + c) % d;
  }
  return int(result);
}

void FillPrefixHashes(const std::string& s, std::vector<int>& hashes) {
  int hash = 0;
  hashes.resize(s.size());
  int a_in_power_i = 1;
  for (int i = 0; i < s.size(); ++i) {
    hashes[i] = hash = (hash + s[i] * a_in_power_i) % simple;
    a_in_power_i = a_in_power_i * a % simple;
  }
}

int main() {
  std::string s;
  s = "abbabaabbaababba";

  std::cout << s.c_str() << std::endl;
  std::cout << my_hash(s, simple) << std::endl;

  std::vector<int> hashes;
  FillPrefixHashes(s, hashes);
  return 0;
}