백준 15829번 <Hashing> - C++

 

 

https://www.acmicpc.net/problem/15829
 
아니 좀 블로그틱하게 써보려했더니 미리보기 왜 안 되냐?
 

암튼 해시함수 그 그거있잖아 매핑해 주는 함수 그래서 공식대로 간단하게 썼더니 달랑 50점 나오더라? 구글링 해 보니까 이게 엄청 큰 수가 들어와버려서 서브태스크 범위를 벗어나서그럼. 그래서 모듈러 연산방법에 대해서 좀 알아보고, 해시함수 모듈러 연산 적용에 대한 수식 간단하게 쓸 거임
 
$$ Hashing\, Function\quad H = 
\left ( \sum_{i=0}^{l-1}a_ir^{i} \right ) \ mod\ M$$
 
$$H\,=\,\left ( a_0r^0+a_1r^1+a_2r^2+\cdots+a_{l-1}r^{l-1} \right )\,mod\,M$$
 
$$=\,\left ( a_0r^0\,mod\,M+a_1r^1\,mod\,M+a_2r^2\,mod\,M+\cdots+a_{l-1}r^{l-1}\,mod\,M \right )\,mod\,M$$
 
 
$$ = 
\left ( \sum_{i=0}^{l-1}a_ir^{i}\,mod\,M \right ) \ mod\ M $$
 
잠시 부분만 떼어 와서,
$$ a_ir^{i}\,mod\,M \,=\,\left ( \left ( a_i\,mod\,M\,\times\,r^i\,mod\,M\, \right ) \right )\,mod\,M$$
 
근데 문제에서 $a_i$는 M만큼 크지 않으므로
$$ \left ( a_i\,\times\,\left (r^i\,mod\,M\, \right ) \right )\,mod\,M$$이다.
 
$$\therefore H = 
\left ( \sum_{i=0}^{l-1}a_ir^{i} \right ) \ mod\ M$$
 
$$ =\,\sum_{i=0}^{l-1}\left [   \left\{ a_i\,\times\,\left ( r^i\,mod\,M \right )   \right\}\,mod\,M         \right ]\,mod\,M$$
 
거짓말 안 치고 수식 LaTeX타이핑 하는 데만 40분 걸렸다 문제보다 오래 풀었다..
아무튼 코드에서는 요렇게 구현했다.

for(int i=0; i<l; i++){
    int letter = str[i]-96;
    total += (letter*r)%M;
    total %= M;
    r = (r*31)%M;
  }

letter은 $a_i$를 의미하고, r에는 계속 31이 곱해지면서 $r^i$가 된다
세 번째 줄 total에는 최종 식의 중괄호 밖, 네 번째 줄은 대괄호 밖, 다섯 번째 줄은 $r^i\,mod\,M$을 연산한다.
 
전체 코드는 이러하다

#include <algorithm>
#include <cmath> //C++
#include <iostream>
#include <math.h> //C
#include <string>
#include <vector>
#include <queue>
#define M 1234567891

using namespace std;


int hashing(string str, int l){

  long long int r=1;
  long long int total=0;
  for(int i=0; i<l; i++){
    int letter = str[i]-96;
    total += (letter*r)%M;
    total %= M;
    r = (r*31)%M;
  }
  
  return total;
}

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int l;
  cin >> l;

  string str;
  cin >> str;
  
  int total = hashing(str, l);
  cout << total ;
  return 0;
}