다항식 문자열 해싱

두 부분 문자열이 같은지 확인해야 하는 경우가 많습니다. 문자를 하나씩 비교하면 느리므로 각 문자열을 하나의 숫자로 바꿉니다. 🔢

해시는 문자열을 하나의 정수로 대응시킵니다. 두 문자열이 다르면 해시도 거의 항상 다릅니다.

각 문자를 p진법의 숫자로 봅니다. 이러한 다항식 관점은 문자열을 하나의 큰 가중 합으로 바꿉니다.

31과 같은 소수 밑과 큰 소수 모듈러를 선택합니다. 모듈러 연산을 사용하면 숫자를 작게 유지하고 오버플로를 피할 수 있습니다.

문자열을 순회하면서 호너의 법칙으로 각 문자를 차례로 합치고, 매 단계마다 모듈러 연산을 적용합니다.

각 위치에 대한 접두사 해시를 저장합니다. 그러면 두 해시를 빠르게 뺄셈하여 어떤 부분 문자열의 해시도 구할 수 있습니다.

밑의 거듭제곱도 미리 계산합니다. 뺄셈할 때 두 접두사의 자릿수를 맞춰 주는 역할을 합니다.

s[l..r]의 해시는 두 접두사 해시를 뺀 뒤 거듭제곱을 곱해 크기를 맞춘 값입니다. 질의 하나를 상수 시간에 처리할 수 있습니다.

서로 다른 두 문자열이 같은 해시를 가질 수 있으며, 이를 충돌이라고 합니다. 드문 일이지만, 대회에서는 때때로 충돌을 일으키도록 입력을 구성하기도 합니다.

두 개의 서로 독립적인 모듈러를 사용하고 두 해시를 모두 비교하세요. 두 해시에서 동시에 충돌할 가능성은 현실적으로 거의 없습니다.

해싱은 부분 문자열 비교, 반복 구간 찾기, 패턴 검색에 활용됩니다. 매우 유연한 다용도 도구입니다.

많은 부분 문자열을 안전하게 비교할 때 알맞은 도구를 선택하세요.

이제 문자열을 다항식 해시로 변환하고, 임의의 부분 문자열을 O(1)에 조회하며, 충돌을 방지할 수 있습니다. 🚀