[C++] BOJ (백준) 15829 : Hashing

문제

15829번: Hashing (acmicpc.net)

15829번: Hashing

코드

#include <iostream>

#define R 31
#define M 1234567891

using namespace std;
typedef long long int lld;

lld R_pow(int n) {
  lld res = 1;
  for (int i = 0; i < n; i++) {
    res *= R;
    res %= M;
  }
  return res;
}

lld hashing(int l, const string &s) {
  lld res = 0;
  for (int i = 0; i < l; i++) {
    res += (s[i] - 'a' + 1) * R_pow(i);
    res %= M;
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int l;
  string s;
  cin >> l >> s;
  cout << hashing(l, s);
  return 0;
}

설명

mod(%) 연산에 대해 다음이 성립한다.
(a + b) mod n = (a mod n + b mod n) mod n
(a * b) mod n = (a mod n * b mod n)

오버플로우가 일어날 수 있기 때문에 모든 자료형은 long long int로 바꾸고,
계산 중간과정에서 계속 % 연산을 해준다.