팰린드롬

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 문자열 문제에서 자주 등장하는 개념이다.

주어진 문자열의 부분 문자열에서 가장 긴 팰린드롬을 쉽게 찾을 수 있는 $\BigO{N}$알고리즘이 존재한다. Manacher's Algorithm이라고 하는데 코드도 짧고 이해하기도 쉬워서 한 번 알아두면 유용하게 사용할 수 있다.

먼저 팰린드롬을 구할 때는 길이가 홀수인 팰린드롬과 짝수인 팰린드롬을 따로 생각해야 한다. 이것이 좀 골치 아프므로 한 가지 트릭을 사용하는데 주어진 문자열에서 문자 사이사이마다 더미 문자를 집어넣는 것이다. 예를 들어, "ababa"에서 팰린드롬을 찾는다고 하면 문자열을 "#a#b#a#b#a#"로 바꾸는 것이다. 이제 각 i에 대해서 S(i-x,i]=S[i,i+x)인 x의 최대값을 구하는 것으로 문제를 해결할 수 있다. 각 i에 대해서 이 x 값을 p[i]라 하자.

이제 한가지 사실만 알면 되는데 다음 그림을 보면 쉽게 이해할 수 있다.

여태껏 찾은 팰린드롬 중에서 x+p[x]가(팰린드롬의 오른쪽 경계) 가장 큰 x가 j라고 하자. 현재 p[i]를 구하려고 하는데 i<j+p[j]라면 p[i]는 최소한 \(\min(j+p[j]-i,p[2j-i])\) 이상이다.

S(j-p[j],j]=S[j,j+p[j])이므로 p[2j-i]가 j+p[j]-i보다 작은 경우, p[i]는 p[2j-i]와 동일한 값을 가질 수 밖에 없다. p[2j-i]가 j+p[j]-i보다 크거나 같은 경우, S(j-p[j],j+p[j])를 벗어나는 범위에 있는 문자에 대해서는 어떠한 예상도 할 수가 없어서 p[i]값을 섣불리 정하지는 못하고 최소한 j+p[j]-i이상임을 알 수 있다. 따라서, p[i]는 최소한 $min(j+p[j]-i,p[2j-i])$이상이다.

이 사실만 알아도 $\BigO{N}$에 모든 p[i]를 구할 수 있다.
void manacher(){ for(int i=0,j=0;i<N;i++){ if(i<j+p[j])p[i]=min(j+p[j]-i,p[2*j-i]); while(i-p[i]>=0&&i+p[i]<N&&S[i-p[i]]==S[i+p[i]])p[i]++; if(i+p[i]>j+p[j])j=i; } }
위 코드가 왜 $\BigO{N}$에 동작할까? for문 내에 있는 while문은 i+p[i]와 j+p[j]가 같을 때만 실행된다. 그렇지 않은 경우에는 그림에 나온 경우와 같이 S[i-p[i]]와 S[i+p[i]]가 같을 수가 없다. 또한 while문 안에서는 i+p[i]가 계속 증가한다. i+p[i]는 최대 N까지 밖에 커질 수가 없으므로 위 코드는 $\BigO{N}$만에 모든 p[i]를 계산할 수 있다.

각 i에 대하여 S(i-p[i],i+p[i])는 팰린드롬이고 S(i-p[i]+1,i+p[i]-1),S(i-p[i]+2,i+p[i]-2),...,S(i,i)까지 \(\sum{p[i]+1}\)개의 부분문자열 모두 팰린드롬이다. 그 중에서 절반은 더미노드 때문에 생긴 것이어서 실제로 \(\sum{p[i]/2}\)개 만큼의 팰린드롬이 존재한다.