그래서 해시 함수가 뭐에요? timer 1s memory 32MB

해시 함수란 임의의 길이의 데이터를 받아 고정된 길이의 데이터로 가공하여 내보내는 함수이다. 이러한 해시 함수는 주로 자료의 저장과 탐색에 사용된다.

영문 소문자(a, b, ..., z)로만 구성된 문자열 S를 입력받아. a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여하자. 만약 문자열 S가 "abbc"라면 이를 수열로 변환하면 \{1, 2, 2, 3, 1\}로 나타낼 수 있다.

해시 값을 계산하기 위해 문자열을 하나의 정수로 치환하고자 한다. 이를 위해 문자열을 수열로 변경하고, 이 변경된 수열의 값을 모두 더한다. 고정된 길이의 데이터로 가공하여야 하기에 M으로 나눈 나머지를 사용한다. 이를 수식으로 표현하면 아래와 같다.

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

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 데이터의 길이는 제한되어 있기에 비둘기 집의 원리에 의하여 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 이에 개선책을 생각해보자.

수열의 각 항마다 고유한 계수를 부여하면 순서가 달라졌을때 해시 함수의 결과가 달라진다. 그럼 특정한 숫자 r를 항의 번호 i만큼 거듭제곱해서 곱해준 다음 더하자. 이를 수식으로 표현하면 아래와 같다. 

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

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이기에 우리는 이 문제에 한하여 r의 값은 26보다 큰 소수인 31로 설정하고, M의 값은 소수인 1\,000\,000\,007로 정한다.

입력으로 주어진 문자열의 해시 값을 위 식을 이용하여 계산하는 프로그램을 작성하자.