15829번: Hashing
APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정
www.acmicpc.net
1. 풀이 방법
- 해싱에 대한 기본 정의를 알고 그대로 구현하면 된다.(50점).
2. 주의 사항
- 모드연산에 대한 변형이 살짝 필요하다.
- (A+B) % MOD = (A%MOD +B%MOD) % MOD (이 문제에서는 필요없지만 뺄셈도 같다.)
- (A*B) % MOD =(A%MOD * B%MOD) % MOD
-(50점)
3. 나의 코드
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int L;
cin >> L;
string s;
cin >> s;
long long mul = 1;
long long result = 0;
for (int i = 0; i < L; i++) {
result =(result+((s[i]-'a'+1)*mul))%1234567891;
mul = (mul * 31) % 1234567891;
}
cout << result<< "\n";
return 0;
}