Intro
ACM-ICPC 등에서 주로 출제되는 문자열 문제는 일반적으로 KMP, Suffix Array, Trie, Aho-Corasick 등의 자료구조나 알고리즘을 사용해서 해결하는 것이 정해인 경우가 많습니다. 하지만, 그 중 많은 문제는 정해를 사용하지 않고도 운에 맡기기만 한다면 비교적 쉽게 해결 가능합니다. 이럴 때 사용하는 기법이 바로 해싱(Hashing)입니다. 해싱은 문자열을 어떤 숫자와 1대1로 대응시킴으로서, 전처리 이후 문자열의 비교와 검색을 사실상 $O(1)$ 에 가능하게 해 줍니다. 이 해싱의 강력한 특징을 이용하면, 문자열 문제들을 날로 먹을 수 있는 경우가 꽤 있습니다. 이 글에서는 그러한 문제들 중에서도 쉬우면서도 나름 특이한 경우들을 다룹니다. 글의 많은 부분은 https://codeforces.com/blog/entry/60445 을 참조했음을 밝힙니다. 또한, 글을 읽는 독자가 롤링 해시의 기초적인 구현을 알고 있다고 가정하겠습니다. 시간복잡도에서의 문자열은, 별도의 설명이 없으면 문자열의 길이를 나타냄을 알립니다.
문자열 검색/비교 대체하기
가장 기초적인 해시의 활용법인 만큼, 특별한 부분은 없음에도 불구하고 간략하게 짚고 넘어가려고 합니다. 어떤 문자열 $A$에서 다른 문자열 $B$를 검색하는 것은 KMP 알고리즘을 활용하여 $O(A+B)$에 할 수 있지만, 해싱으로도 동일한 복잡도에 수행할 수 있습니다. 문자열 $A$의 substring 중 길이가 $B$인 것을 모두 해싱해 둡시다. 그러면 발생한 모든 해싱값에 대해 $B$의 해시값과 같은지를 비교해 줌으로서 $B$가 $A$에서 등장하는 모든 위치를 빠르게 찾아줄 수 있습니다.
어떤 문자열 $A$와 $B$가 적절하게 해싱되어 있다면, 이 두 문자열의 lexiographical한 비교도 $O(\log \min (A,B))$만에 가능합니다. 사전순 비교는 두 문자열이 처음으로 달라지는 지점을 찾고 그 지점에서의 문자를 비교하는 것과 동일하므로, 이분 탐색을 이용해 문자열의 해시값이 처음으로 달라지는 지점을 찾은 후에 그 지점에서 $A$와 $B$의 문자를 비교하면 됩니다.
Longest Common Substring
일반적으로 Suffix Array를 이용해서 해결하는 가장 긴 공통 부분 문자열의 길이를 찾는 문제도 해싱으로 빠르게 해결 가능합니다. 다음과 같은 결정 문제를 생각합시다: 길이가 $k$ 이상인 공통 부분 문자열이 존재하는가? 길이가 $k$ 이상인 공통 부분 문자열이 존재한다면 길이가 $k$ 미만인 공통 부분 문자열도 반드시 존재하므로, 이를 이분 탐색을 이용하여 확인해줄 수 있습니다. 한 번의 결정 문제를 해결하는 것은 문자열 $A$와 $B$를 각각 길이 $k$로 해싱한 다음 같은 해시값이 존재하는 지 판별하는 것과 같으므로, 총 시간복잡도는 $A>B$일 때 $O((A+B) \log B)$ 가 됩니다.
같은 느낌으로 한 문자열 $S$에 두 번 이상 등장하는 Substring을 찾는 문제도 이분 탐색을 적용한 다음, 두 번 이상 등장하는 해시값이 존재하는지 판별하는 문제로 환원하여 해결할 수 있습니다. Substring이 겹치지 않아야 한다면 Z 알고리즘 같은 이상한 알고리즘을 쓰는 대신 해시값을 저장할 때 시작 지점을 저장해서 자료구조를 이용해 처리해줄 수도 있습니다(NYPC 2018 예선 봇 탐지).
Prefix Hash Table
다음으로 해결할 수 있는 문제를 소개하기 전에 혹시 모르시는 분들을 위해서 Prefix Hash Table에 대해서 설명하려고 합니다. Prefix Hash Table이란 그냥 단순하게 문자열 $S$에 대해 1번째 문자부터 $S$번째 문자까지 처음 $x$개의 문자로 구성된 문자열의 해시값을 저장해 놓은 것을 말합니다. 일반적으로 롤링 해시에서는 길이를 고정시키고 문자를 하나씩만 변화시키면서 해시값을 계산하기 때문에, 문자가 추가될 때 새로운 값을 더해 주고 문자가 제거될 때 추가했던 값을 빼 주는 식으로 간단하게 계산할 수 있었습니다. 하지만 어떤 문자열에 대하여 임의의 substring의 해시값을 구하고 싶다면 어떨까요? 그렇게 어렵지 않습니다.
편의를 위해 0-index를 사용하겠습니다. $k$번째 문자까지의 해시값은 해시 상수가 $p$이고 모듈러가 $M$일 때 , $\displaystyle H_k = \sum_{i=0}^{k} S_i \cdot p^i \space mod \space M $ 이 됩니다. 이때 $L$번째 문자부터 $R$번째 문자까지의 substring 해시값은 $\displaystyle \sum_{i=L}^{R} S_i \cdot p^{i-L} \space mod \space M $ 이므로, $\displaystyle \frac{ H_R - H_{L-1} }{ p^L } $ 로 계산할 수 있습니다. 모듈러가 있는 상황에서 나누기 위해서는 모듈러 인버스를 찾아야 하는데, $M$을 적절한 소수로 미리 설정해 두었다면 페르마 소정리를 통해 $p^k$에 대한 모듈러 인버스를 빠른 거듭제곱법으로 $O(\lg K)$에 찾아줄 수 있습니다. 따라서 처음에 Prefix Hash Table을 $O(S)$에 계산해 둔다면 이후에는 임의의 substring의 해시값을 $O(\lg S)$에 찾아줄 수 있겠습니다. 쿼리가 꽤 많은 것이 보장된다면 모든 경우의 모듈러 인버스를 $O(S)$에 미리 전처리 해둘 수도 있습니다. 이건 문제에 따라서 다르게 쓸 수 있는 영역이겠네요.
팰린드롬과 관련된 문제들
문자열의 동일 여부를 $O(1)$에 판단할 수 있다는 특성 덕분에, 팰린드롬에 관한 문제들을 효율적으로 해결할 수 있습니다.
부분 문자열 팰린드롬
문자열 $S$에 대해, S의 부분 문자열 중 길이가 $k$인 팰린드롬을 모두 찾아야 합니다. Manacher’s Algorithm을 사용해서 $O(S)$로 풀 수 있는 문제지만, 역시 해싱으로도 풀 수 있습니다. 문자열 $S$를 뒤집은 문자열 $T$를 만듭니다. $S$에서는 앞에서 뒤로, $T$에서는 뒤에서 앞으로 진행하면서 길이가 $k$인 롤링 해시를 진행합니다. $S$의 경우에는 하던 대로 롤링 해시를 해주면 되고, $T$인 경우에도 모듈러 인버스를 미리 전처리 해두면 $S$와 비슷하게 롤링 해시를 계산해 줄 수 있습니다. 동시에 롤링 해시를 진행하게 되면 결과적으로 길이가 $k$인 같은 부분의 문자열을 정방향/역방향으로 보고 있는 꼴이 되므로, 해시값이 같은 경우를 세 주면 간단하게 답을 구해줄 수 있습니다.
팰린드롬과 쿼리
문자열 $S$가 있고, $Q$개의 쿼리가 주어진다고 합시다. 각 쿼리에는 시작 지점 $L_i$와 $R_i$가 주어지는데, $L_i$번째 문자부터 $R_i$번째 문자까지의 Substring이 팰린드롬인지를 판별해야 합니다. 어떻게 하면 이를 효율적으로 해결할 수 있을까요? 위의 Prefix Hash Table을 응용해서 해결해봅시다. $S$를 뒤집은 문자열 $T$를 구한 후 두 문자열에 대해 Prefix Hash Table을 구합니다. 그 이후 각 쿼리에 대해 주어진 구간의 해시값을 $O(\lg S)$에 구해줄 수 있고 $S$와 $T$에서 두 값이 같은 지 확인해주면 됩니다. 총 시간복잡도는 $O(Q \lg S)$ 입니다.
Cyclic Shift
롤링 해시의 구조 덕분에, 어떤 문자열을 원형으로 Cyclic Shift 하는 상황에서의 여러 문제를 해시로도 빠르게 해결할 수 있습니다.
Lexiogrphically Minimal Cyclic Shift / Sorting Cyclic Shift
문자열 $S$가 주어질 때, $S$를 Cyclic Shift 하는 상황에서의 Lexiographically Minimal한 문자열을 찾아야 합니다. Suffix Array 등을 짤 수도 있겠지만 해싱으로 구현하면 매우 쉽게 구현이 가능합니다. 이 경우에는 간단하게 $S$를 두 번 이어붙여 새로운 문자열 $S’$를 만든 다음, 이 문자열에서 길이가 $S$인 롤링 해시를 진행하면서 한 번 진행할 때 마다 현재 Minimum과 비교를 진행해주면 됩니다. 총 시간복잡도는 $O(S \lg S)$가 됩니다. 비슷하게 모든 Cyclic Shift를 정렬하는 것도 할 수 있습니다. 비교 연산자를 해싱을 통해서 재정의해주면 되고, 시간복잡도는 마찬가지로 $O(S \lg ^2 S )$ 가 됩니다. 다만 이 경우에는 Stable하게 정렬을 해주는 것이 상수 측면에서 유의미한 이득을 본다고 합니다.
Substring of Cyclic Shift
문자열 $S$와 $T$가 주어질 때, $S$의 cyclic shift 중 $T$의 substring과 일치하는 것이 몇 개나 있는지 판별해야 하는 문제입니다. $S$를 두 번 늘려서 $S’$으로 만듭시다. $S’$에서 길이가 $S$인 모든 해시값을 뽑아내어 정렬한 다음, $T$의 길이가 $S$인 해시값을 롤링 해시로 뽑아내어 이분 탐색을 이용해 찾아주면 됩니다. 시간복잡도는 $O(S \lg S)$가 되겠습니다.
기타 문제들
Infinite extension Suffix
문자열 $S$가 있을 때 $S$를 무한히 이어 붙인 문자열 $I$가 있다고 합시다. $S$의 Suffix들을 $S_i$라고 했을 때, $S_i$를 무한히 이어 붙인 문자열과 $I$를 무한히 이어 붙인 문자열이 같다면 이를 좋은 Sufffix라고 합시다. 과제는 좋은 Suffix의 개수를 세는 것입니다.
매우 느린 해법을 한 가지만 생각해 봅시다. 일단 $S$를 뒤집어서 $S’$를 만든 다음, prefix에 대한 문제를 해결한다고 생각할 수 있습니다. 길이가 $m$인 prefix $S_m$에 대해, $S$의 길이를 $n$이라고 하면 $S_m$을 $n$개, $S$를 $m$개 이어 붙은 문자열을 각각 만들 수 있습니다. 이 이후로는 주기적으로 계속 반복될 테니, 이 두 문자열이 일치하는 지 판별하면 될 것입니다. 하지만 이건 너무 느립니다. 자그마치 $O(m^2 n)$에 달하는 시간복잡도입니다. 이걸 어떻게 하면 줄일 수 있을까요?
식을 깔끔하게 정리해 봅시다. $S$ 대신 $S_n$을 써서 $S_n$과 $S_m$이 무한히 반복되었을 때 겹치는지를 확인하려면, 다음과 같은 식을 쓸 수 있을 것입니다. 0-index 기준으로
\[\displaystyle S_m = (\sum_{i=0}^{n-1} p^{i \cdot m}) (\sum_{i=0}^{m-1}S[i] \cdot p^i)\] \[\displaystyle S_n = (\sum_{i=0}^{m-1} p^{i \cdot n}) (\sum_{i=0}^{n-1}S[i] \cdot p^i)\]와 같습니다.
뒤쪽 해시는 Prefix Hash Table을 구성하면 빠르게 계산할 수 있다고 치고, 앞쪽은 어떻게 하면 빠르게 계산할 수 있을까요? 그냥 간단하게는 등비수열 공식으로 $a=p^m$ 또는 $a=p^n$일때 $ \displaystyle \frac{ a^{k-1}}{a-1}$로 계산할 수 있다고 생각할 수 있습니다. 그러나 생각해 보면 $p$와 달리 $a$는 소수가 아니기 때문에 모듈러 인버스를 사용할 수가 없습니다. 그래서 분할 정복을 이용해 홀수 항과 짝수 항을 나눠서 빠르게 계산하는 테크닉을 사용해야 합니다. $\displaystyle sum(a,t) = \sum_{i=0}^{k-1} a^i$라고 하면, $t$가 짝수일 때 $\displaystyle (1+a) \cdot sum(a^2, \frac{t}{2})$ 로 표현이 가능하기 때문에 빠르게 계산이 가능합니다. 더 정확하게는, 제곱 횟수 $k$에 대해서 $O(\lg k)$입니다.
결과적으로 앞쪽 식은 빠른 거듭제곱으로, 뒤쪽 식은 Prefix Hash Sum으로 계산이 가능하니 하나의 길이에 대해서 $O(\lg n)$ 시간에 확인이 가능한 것을 알 수 있습니다. 총 시간 복잡도는 $O(n \lg n)$입니다.
두 문자열 중 하나에서 두 문자를 교체할 수 있을 때 Longest Common Prefix
이름만 들어도 끔찍한 문제고, $O(n)$ 해법이 존재하지만, 해싱으로 날로 먹는 방법이 역시 존재합니다. 일단 해야 하는 관찰은 바꿔야 하는 문자 중 하나는, 두 문자열을 $S$와 $T$라고 했을 때 현재 $S$와 $T$의 Longest Common Prefix의 바로 다음 문자라는 것입니다. 그러면 이 문자와 뒤에 있는 어떤 문자를 서로 교체했을 때 얻을 수 있는 Common Prefix의 최댓값을 구하는 문제가 됩니다.
어차피 하나를 교체하고 나서는 뒤가 없습니다. 그 다음부터는 그냥 추가되는 Longest Common Prefix의 길이의 최댓값을 찾으면 됩니다. 따라서 모든 문자에 대해서 모두 바꾸는 것을 시도해볼 수 있습니다! 이건 LCP 길이에 대한 이분 탐색으로 해결해 줄 수 있습니다. 만약 바꾼 두 문자가 이분 탐색하는 범위에 포함되지 않으면 해시값을 바꿔 줄 필요가 없습니다. 만약 포함된다면, 그에 따라서 적절하게 해시값을 잘 수정해줘야 합니다. $p$의 거듭제곱을 모두 계산해 두고 그에 맞춰서 앞쪽 문자의 해시값에 적당한 수를 곱하고, 뒤쪽 문자의 해시값에 적당한 수를 나눠주면 됩니다. 총 시간복잡도는 $O(S \lg S)$가 됩니다.
문자 추가, 삭제, 변경을 빠르게 하기
조금 더 추해지기 위해서, 문자열이 변경되었을 때 해시값을 빠르게 변경하는 방법을 생각해 볼 수 있습니다. 우리가 쓰는 Rabin Fingerprint에서, 어떤 문자열 $S$에 대한 해시값은 길이가 $n$일 때 $\displaystyle \sum_{i=0}^{n-1}S[i] \cdot p^i$ 입니다. 다른 말로 하면, 특정한 자료구조에 각 문자에 대응하는 해시값을 분리해서 저장해 두고 이를 더해서 사용할 수도 있다는 말이 됩니다.
이럴 때 사용하는 자료구조로 많이 우려먹혔던 세그먼트 트리를 사용할 수 있습니다! 세그먼트 트리의 각 리프 노드에 문자에 대응하는 해시 값을 저장합시다. $i$번째 문자가 하나 변경되면 그 문자에 해당하는 리프 노드의 값을 $p^{i-1} \cdot (S_{new}-S_{before})$ 만큼 증가시켜 줄 수 있습니다. 어떤 특정한 Substring의 해시값도 $L_i$부터 $R_i$까지의 문자라면 $ \displaystyle \frac {Query(L_i,R_i)} {p^{L_i - 1}}$ 로 구해줄 수 있습니다.
문자 삽입은 어떻게 할까요? $x$번째 위치에 문자를 삽입하려면, $x$번째 위치부터 끝 위치까지 삽입하는 값 $t$에 대해 $p$를 곱하고 $t \cdot p^{x-1} $을 더해 줘야 합니다. 이 경우에는 일반적으로 관리했을 때와 달리 인덱스가 꼬일 수 있으니, 별도의 처리 방안을 마련해주어야 합니다. Splay Tree 등을 활용하는 것도 괜찮은 대안이 될 것입니다. 문자열 문제는 아니지만, 이와 같은 방식을 활용하여 풀 수 있는 문제를 소개하는 글로 rdd6584님이 작성하신 http://www.secmem.org/blog/2020/01/19/Rabin-fingerprint-for-problem-solving/ 가 있습니다.
마치며
해싱은 많은 문제에 포괄적으로 적용할 수 있는 강력한 알고리즘입니다. 물론 문자열 문제를 처음 봤을 때 다른 해법을 생각하지 않고 무작정 해싱만을 적용하려고 시도하는 것은 지양해야 할 것입니다. 그럼에도 불구하고 ICPC와 같이 무조건 솔브를 하나 추가해야 하는 상황에서 해싱의 적절한 활용은 매우 어려운 문자열 문제도 쉽게 풀게 해주는 황금 열쇠가 될 수 있으니, 해싱으로 풀릴 것 같은 문제는 정해로 풀어 본 이후 해싱으로도 풀어 보는 것을 추천합니다. 이 글에서 소개된 기법 말고도 해싱으로 풀 수 있는 다양한 문제들이 있습니다. 출제자의 의도를 무시하는 것을 좋아하고, 문제 하나를 날로 먹는 것을 좋아하는 사람들이라면, 다른 문제들에도 꼭 한 번 도전해보시기를 바랍니다. :)