매내처 없이 해싱을 이용하여 푸는 방법

 

매내처는 어떤 문자열 $S$에 대해 모든 위치를 중심으로 하는 가장 긴 팰린드롬 부분 문자열의 길이를 $O(|S|)$에 구할 수 있습니다. 하지만 매내처는 이해하기 까다롭고 생각하고 하는 일이 명확하다보니 이 알고리즘이 대회에 나오는 빈도가 낮습니다. 따라서 충돌만 피할 수 있으면 어떤 부분 문자열 $S'$이 존재하는지 빠르게 파악하는 해싱을 이용하여 가장 긴 팰린드롬 부분 문자열이 있는지, 그리고 그 길이가 최대 몇인지 알아보겠습니다.

 

먼저, 여기서 말하는 문자열에서 해싱은 롤링 해시을 이용한 라빈-카프를 의미합니다. 여기서는 매내처를 대체하는 방법에 대해서만 설명하겠습니다. 그리고 이 문서는 모두 1-based index로 작성되었습니다.

 

문자열 $S$가 있습니다. 그리고 $S$를 뒤집은 문자열 $R$이 있습니다. 각각의 문자열의 prefix에 대한 해시 값을 미리 계산해둡시다. $S[l, r]$를 $S$의 $l$번째부터 $r$번째까지의 부분 문자열이라고 정의하면, $S[l, r]$이 팰린드롬이라는 것은 $S[l, r] = \text{reverse}(S[l, r])$를 의미하겠네요.

 

이 $S[l, r]$이 팰린드롬인지 확인하기 위해서 $S[l, r]$의 해시 값과 $R$에서 대응되는 구간의 해시 값을 비교하면 됩니다. 그럼 아까 정의했던 문자열 $R$을 이용하여 $R$의 어떤 구간을 봐야하는지 알아봅시다.

 

$S$에서 인덱스 $i$에 있는 문자는 $R$에서는 인덱스 $|S|-i+1$에 위치합니다. 따라서 $S[l, r]$에 대응되는 것은 $R[|S|-r+1, |S|-l+1]$이 됩니다. 예를 들어서 $S$는 "abcdcbg"라는 문자열이라고 해 봅시다.

예를 들어 $S[3, 6] = cdcb$이고 이에 대응하는 $R$은 $R[2, 5] = bcdc$이다.

 

그러면 어느 구간 $[l, r]$이 팰린드롬인지 확인하는 건 $S[l, r]$의 해시 값과 $R[n-r+1, n-l+1]$의 해시 값이 같으면 팰린드롬이겠죠. 물론 충돌이 일어나지 않는다는 전제 조건이 필요하겠네요. 이 방법으로 BOJ 11046을 간단하게 풀 수 있습니다. 매내처랑 마찬가지로 각 쿼리를 $O(1)$에 풀 수 있습니다.

 

 

 

쿼리가 많아서 FASTIO를 사용했고, 위에 작성한 대로 쿼리에서 범위만 주면 빠르게 팰린드롬인지 알 수 있습니다. 여기서는 모듈러를 $10^{9}+9$로 고정하고 base를 $[256, 10^{4}]$로 설정하였습니다.

 

그러면 $S[l, r]$가 팰린드롬 문자열인지 아닌지는 알겠는데, 문자열이 주어졌을 때 가장 긴 팰린드롬 부분 문자열의 길이나 팰린드롬인 부분 문자열들의 개수는 어떻게 구하나요? 이는 이분 탐색을 이용하면 풀 수 있습니다.

 

간단하게 생각해보면 길이가 $L$인 팰린드롬이 문자열 $S$에 있는가는 $S[1, 1+L-1]$부터 $S[|S|-L+1, |S|]$까지 전부 봐서 팰린드롬이 하나라도 있으면 되겠네요! 만약에 길이 $L$인 팰린드롬이 문자열 $S$에 있다면 하한을 늘리면서 이분 탐색을 하면 되지 않을까요? 안타깝게도 이 방식은 통하지 않습니다. 위의 문자열 $S$만 봐도 $L=3$인 팰린드롬 문자열은 존재하지만 $L=4$인 팰린드롬인 문자열은 존재하지 않고, $L=5$인 팰린드롬은 또 존재하네요. 즉 단조성을 띄지 않기 때문에 이 방식의 이분 탐색을 이용할 수 없습니다.

 

문제를 다시 보면, 팰린드롬은 항상 어떤 중심을 기준으로 좌우 대칭입니다. 그래서 길이를 기준으로 하지말고 중심을 기준으로 팰린드롬인지 파악해봅시다. 그리고 홀수 길이의 팰린드롬의 경우는 어떤 문자 하나를 중심으로 기준 잡을 수 있지만 짝수 길이의 팰린드롬은 그럴 수 없으므로 두 문자를 중심으로 기준을 잡아봅시다.

제일 긴 홀수 팰린드롬은 $S[2, 6] = bcdcb$이므로 길이가 $5$인 팰린드롬 문자열이다.

 

먼저 홀수 길이의 팰린드롬부터 살펴보죠. 위의 문자열 $S$를 보면 $S[2, 6]$은 $L=5$인 홀수 길이의 팰린드롬 문자열입니다. 그러면 중심 인덱스 $i=4$이고, 반지름 $r=2$인 팰린드롬으로 $S[i-r, i+r] = S[2, 6]$이라고도 생각 할 수 있겠네요. 그리고 그 길이 $L=2r+1=5$로 딱 맞습니다. 중심 $i$를 고정하면 반지름 $r=0$, 즉 길이가 $1$인 문자열은 항상 팰린드롬이고 어떤 $r = k$에서 팰린드롬이 불가능하다면 $r > k$인 팰린드롬은 존재하지 않습니다. 따라서 중심 $i$에 대해서 $r=0, 1, 2, \cdots$ 에 대한 팰린드롬은 단조성을 띄게 됩니다. 중심을 고정하고 반지름에 대해 이분 탐색을 하면 되겠군요! 그럼 중심 $i$를 $1$부터 $|S|$까지 확인해서 최대가 되는 $r$를 찾는 문제로 바꿀 수 있게 됩니다. 물론 팰린드롬의 최대 길이는 $|S|$를 넘길 수 없기 때문에 $r$의 상한을 적절히 조절하여 순회 해주시면 되겠습니다.

여기서 제일 긴 짝수 팰린드롬은 $S[2, 5]=bccb$이고 제일 긴 홀수 팰린드롬은 $S[5, 7]=bfb$이다.

 

다음은 짝수 길이의 팰린드롬을 살펴보겠습니다. 새로운 문자열 $S = abccbfb$를 살펴보죠. $S[2, 5]$은 $L=4$인 짝수 길이의 팰린드롬 문자열입니다. 중심은 두 문자라고 생각하겠습니다. 구체적으로 $bccb$라는 팰린드롬이 있다면 중심은 $cc$를 의미합니다. 인덱스로 적으면 $i$와 $i+1$라고 생각할 수 있겠죠. 여기서는 $i=3$겠네요. 반지름은 $r=1$인 팰린드롬으로 $S[i-r, i+r+1] = S[2, 5]$라고 할 수 있습니다. 그리고 길이는 $L = 2r+2 = 4$입니다. 짝수 길이의 팰린드롬도 마찬가지로 중심을 고정하면 반지름 $r$에 대해서는 단조성이 생기기 때문에 이분 탐색을 할 수 있게 되네요.

 

정리하면 가장 긴 팰린드롬의 길이를 찾기 위해서 홀수 길이든 짝수 길이든 중심을 고정하고 반지름 $r$에 대해서 이분 탐색을 수행합니다. 이때 둘의 차이점은 홀수 길이는 $L=2r+1$이고 짝수 길이는 $L=2r+2$가 됩니다. 또한 홀수는 $S[i-r, i+r]$였다면 짝수는 $S[i-r, i+r+1]$네요. 함수 하나로 충분히 커버 가능하니 잘 짜봅시다.

 

BOJ 13275가 정직하게 가장 긴 팰린드롬 부분 문자열을 구하는 문제네요. 코드를 보면서 알아봅시다.

 

 

위에서 설명한대로 코드 로직이 전부 짜져있는데, 이분 탐색 부분 쪽을 다시 설명해보겠습니다. 먼저 f 함수의 인자는 (문자열 $S$의 길이, 팰린드롬의 중심, 반지름, 홀수(0)/짝수(1))를 의미합니다. 홀수 길이의 경우 for문에서 $i$는 팰린드롬 중심 인덱스입니다. 왼쪽으로는 최대 $i-1$칸까지 갈 수 있고, 오른쪽으로는 최대 $|S|-i$칸 만큼 갈 수 있습니다. 따라서 양쪽 끝 중에서 더 짧은 쪽을 선택합니다. 짝수 길이의 경우 for문에서 $i$는 두 중심 문자열 중에서 왼쪽 문자열의 인덱스입니다. 왼쪽으로는 최대 $i-1$만큼, 오른쪽으로는 최대 $|S|-i-1$칸 만큼 갈 수 있습니다. 따라서 이 값 중 작은 값을 선택해서 반지름 $r$의 상한을 정해줍시다.

 

또한 이 코드를 살짝 변경하면 부분 문자열 중에 회문인 것의 개수도 구할 수 있습니다. BOJ 16163이 그 문제네요.

 

 

한 중심에서 가장 긴 팰린드롬의 반지름 $r$을 찾았다고 하면, 반지름이 $r-1, r-2, \cdots, 0$도 모두 팰린드롬이 됩니다. 따라서 $r+1$를 더해주면 됩니다. 이는 홀수, 짝수 마찬가지입니다.

 

물론 이 풀이에는 매내처보다 시간도 오래 걸리고 해시 충돌이 발생할 수 있습니다. 해시 전처리도 해야하고 슬라이딩 윈도우 느낌으로 이분 탐색도 같이 해야하기 때문입니다. 그래서 $O(N \log N)$이 더 붙는거 같네요. 시간이 넉넉하다면 이 방법을 생각할 수 있고 해시 충돌이나 특정 모듈러 저격 데이터가 걱정이라면 런타임에 밀러-라빈을 이용해서 큰 소수를 랜덤으로 찾아내고 이를 적용하거나 큰 소수 배열을 나열하여 그 소수 중에 랜덤으로 뽑아서 적용하거나, 이중 해시를 사용해서 충돌 확률을 더 낮추는 방법이 있습니다. 물론 시간은 배로 더 들겠죠. 핵이 있는 코드포스에서는 저격을 안 당하기 위해서는 적절히 사용해야 하고 BOJ같이 핵도 없고 재채점이 빈번하지 않는 플랫폼에서는 시간만 넉넉하다면 충분히 뚫어서 정답을 맞출 수 있습니다.