해싱

자료구조 수업을 들어본 적이 있다면 해시 함수라는 말을 들어봤을 것이다. 해시 함수는 임의 길이의 입력을 받아 고정 길이의 출력을 내놓는 함수로, 자료의 저장과 탐색에 널리 쓰인다.

이 문제에서는 앞으로도 유용하게 쓸 수 있는 문자열 해시 함수 하나를 소개한다. 입력 문자열은 영문 소문자(a, b, ..., z)로만 이루어져 있다고 가정한다. 알파벳은 총 26개이므로 각 문자에 고유한 번호를 매길 수 있다. 즉 $a = 1$, $b = 2$, $c = 3$, ..., $z = 26$이다. 이렇게 하면 문자열 하나를 수열 하나로 바꿀 수 있다. 문자열 "abba"는 수열 $1, 2, 2, 1$로 나타낼 수 있다.

해시 값을 구하기 위해 문자열, 즉 수열을 하나의 정수로 바꾸려고 한다. 가장 간단한 방법은 수열의 값을 모두 더하는 것이다. 해시 함수는 출력 범위가 유한해야 하므로 적당히 큰 수 $M$으로 나눈 나머지를 취한다. 식으로 나타내면 다음과 같다.

$H = \sum_{i=0}^{l-1}{a_i} \mod M$

입력으로 들어올 수 있는 문자열은 무한히 많지만 출력 범위는 정해져 있다. 비둘기집 원리에 따르면 서로 다른 문자열이 같은 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하며, 좋은 해시 함수는 충돌을 최대한 적게 일으켜야 한다. 위 함수는 알파벳의 순서만 바꿔도 충돌이 일어나므로 나쁜 해시 함수이다. 이를 개선해 보자.

순서가 달라지면 출력도 달라지게 하려면 어떻게 해야 할까? 수열의 각 항에 고유한 계수를 곱해 주면 된다. 대표적인 방법은 항의 위치 번호만큼 특정한 수를 거듭제곱해서 곱한 뒤 더하는 것이다. 식으로 나타내면 다음과 같다.

$H = \sum_{i=0}^{l-1}{a_ir^i} \mod M$

보통 $r$과 $M$은 서로소인 수로 정한다. 여기서는 $r$은 26보다 큰 소수인 31로, $M$은 1234567891(소수이다)로 정한다.

여러분이 할 일은 위 식으로 주어진 문자열의 해시 값을 계산하는 것이다. 간단해 보이지만 자주 쓰이는 함수이니 기억해 두자.

첫째 줄에 문자열의 길이 $L$이 주어진다. 둘째 줄에 영문 소문자로만 이루어진 문자열이 주어진다. 문자열의 길이는 $L$이다.

주어진 해시 함수와 입력 문자열로 계산한 해시 값을 정수로 한 줄에 출력한다.

거듭제곱을 매번 처음부터 계산하면 수가 매우 커지므로, $r$의 거듭제곱을 앞에서부터 차례로 갱신하면서 매번 $M$으로 나눈 나머지를 취한다. 즉 $p_0 = 1$, $p_{i+1} = (p_i \times r) \mod M$으로 두고 $H = (H + a_i \times p_i) \mod M$을 누적하면 된다. $r^0 = 1$임에 유의한다.