태그:
문자열을 주어진 해시 함수를 이용하여 해싱하는 문제입니다. 문제에 따르면 해시 함수를 \(H=\sum_{i=0}^{n-1} a_i r^i \text{mod} M\), r=31, M=1234567891로 설정했습니다.
문제를 보면 두 서브태스크로 나뉘어있는데, 하나는 길이 5 이하인 문자열에 대해서고, 나머지 하나는 길이 50 이하인 문자열에 대해서 해싱을 해야합니다. 길이 5 이하일 경우는 단순히 sum을 구한 후 mod를 취해도 되겠지만, 길이 50 이하인 경우는 조금 다릅니다. 적당한 문자열에 대하여 해시 연산을 위한 임시 변수를 long long 타입으로 잡아도 범위를 넘어가는 경우가 생깁니다.파이썬은 그런거 없음 그래서 sum의 매 항을 구할 때마다 mod를 씌워줘야 해시값이 보존됩니다. \((a+b) \text{mod} c=a \text{mod} c + b \text{mod} c\)임을 생각하면 후자의 방법으로 계산해도 전혀 문제가 없다는 것을 알 수 있습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-12-15 22:19:54 |