[Algorithm] Manacher's Algorithm

개요

Manacher's Algorithm은 주어진 배열에서 배열의 각 entry를 중심으로 하는 가장 큰 회문(palindrome)의 크기를 구하는 알고리즘이다.

 

Brute Force Approach

이를 단순히 Brute Force로 접근해보자.

총 substring의 개수가 $O(n^2)$이며, 각 substring이 회문인지 아닌지 판별하는데 $O(n)$이 걸린다.

따라서 총 시간복잡도 = $O(n^2) \times O(n) = O(n^3)$ 이다.

 

 

중복 제거

$s=\text{bananax}$가 회문인지 아닌지 판단한다고 하자.

우리는 $\text{bananax}$가 회문이 아니라는 걸 알기 위해 다음과 같은 과정을 거친다.

$s[2] = s[4]$   ->   $s[1] = s[5]$   ->   $s[0] \neq s[6]$

 

우리가 각각의 substring을 모두 회문이 아닌지 체크만 한다면, $\text{bananax}$가 회문이 아니라는 정보만 이용하고, 계산과정에 있었던 $s[2]=s[4], s[1]=s[5], s[0] \neq s[6]$과 같은 정보들을 버리게 되는 것이다. 따라서 이러한 정보를 이용하여 중복 계산을 줄인다면 시간복잡도의 개선을 노릴 수 있을 것이다.

 

조금 생각을 해본다면 각 entry를 중심으로 하는 가장 큰 회문의 크기를 $O(n)$만에 구할 수 있다는 것을 알 수 있다.

 

$\text{abanana}$를 예시로 들면 

 

a	b	a	n	a	n	a
		이 부분이 회문이기 때문에
	이 부분이 회문인지 확인하려면 b와 n이 같은지만 보면 된다.
또한 위쪽이 회문이 아니기 때문에, 이 부분은 절대 회문이 될수 없다.

 

따라서 각각의 중심을 기준으로 길이를 0부터 하나씩 늘려가면, $O(n)$만에 특정 index를 중심으로 하는 가장 큰 회문을 구할 수 있다.

 

총 $O(n)$의 index가 있고, 각 index에 대해서 가장 큰 회문을 찾는데 $O(n)$의 시간이 걸린다.

따라서 이 방법의 시간복잡도는 $O(n) \times O(n) = O(n^2)$이다.

 

아직도 덜 쓴 정보가 있다?

이 정도면 충분히 버려지는 정보없이 잘 만들었다고 보일 수 있다.

$O(n^2)$이면 많은 PS 문제에서 Acceptable한 시간복잡도이기 때문에 더욱 그렇다.

그럼에도 아직도 버려지는 정보가 있다.

 

우리는 다음과 같은 의문을 가져볼 수 있다.

 

각 중심을 기준으로 하는 회문을 길이 1짜리 회문부터 찾아야하는 것인가?

 

여기까지 왔다면 위의 질문에 대한 답이 'No'라는 것을 대략 추측하셨으리라 믿는다.

 

각 index를 중심으로 하는 최대 회문의 반지름을 $A$라고 하고 $A$배열을 채운다고 해보자.

$s=\text{banana}$의 경우

s	b	a	n	a	n	a
A	0	0	1	2	1	0

위와 같은 배열이 채워지게 되는 것이다.

 

만약 $s=\text{abacababa}$에 대해서 $A$배열을 구하는 과정에서 다음과 같은 상황을 가정해보자.

s	a	b	a	c	a	b	a	b	a
A	0	1	0	3	0

 

다음의 올 문자 b는 $s[4]$를 중심으로 하는 길이 $A[4]=3$인 회문 'abacaba'에 포함되어 있다.

우리는 또한 abacaba가 회문임을 알고, $s[6]$과 $s[2]$가 $s[4]$를 기준으로 대칭임을 안다.

따라서 s[0:2]="aba"가 회문이라는 정보를 이용한다면, 추가적인 계산없이 s[5:7]="aba"가 회문이라는 사실을 알 수 있는 것이다.

이 사실을 이용하면, $A[4]$를 0부터 찾을 필요없이 1부터 찾을 수 있게 된다.

 

좀더 엄밀하게 얘기하자면 $A[i]$를 계산하고자 할 때, 현재까지 가장 멀리 뻗어있는 회문을 관리하는 것이다.

회문의 index인 $ind=arg\max(j+A[j])$ 와 그 회문이 얼마나 뻗어있는지의 정보인 $x=\max(j+A[j])$를 매번 계산한다.

 

이 회문 안에 들어가는 범위 내에서는 이미 계산한 $i$의 대칭점인 $i' = 2*ind-i$의 정보를 사용하게 된다.

따라서 0부터 보는 것이 아니라 $\min(A[i'], x-i)$부터 하나씩 늘려가면서 $A[i]$를 찾는 것이다.

 

만약 $i$가 범위에 들어가지 않는다면 $O(n^2)$ 알고리즘과 동일하게 0부터 계산한다.

 

 

시간복잡도는?

시간복잡도를 계산하기 위해서 $A[i]$의 초기값이 어디서 부터 시작하는 지를 체크해야한다.

 

case 1) 초기값이 $A[i']$이고, $A[i']<x-i$일 때,

이미 A[i']를 계산할때, 더 긴 회문이 없다는 계산이 끝났기 때문에, 이 경우에는 바로 $A[i]=A[i']$을 하고 종료한다.

 

case 2) 초기값이 $x-i$이거나 0일 때

이 경우에는 원래 $O(n^2)$ 알고리즘과 똑같이 하나씩 늘리면서 계산하게 된다.

이 때 $x$의 값이 1 증가하게 되는데, $x$는 초기값 0부터 감소하지 않고 1씩 증가만 해서 최종적으로 $n$이 된다.

따라서 case 2는 총 $n$번 시행되게 된다.

 

따라서 시간복잡도는 $O(n)$이 된다.

 

 

일반적인 회문은 어떻게 구하는가?

이 알고리즘은 홀수 길이의 회문만 구할 수 있다는 단점이 있다.

짝수 길이의 회문을 구하기 위해서는 string의 중간에 사용하지 않는 문자를 추가해주는 것이다.

예를 들어서 $s=\text{banana}$ 라면 $s'=\text{b@a@n@a@n@a}$로 변경한다.

이렇게 하면 @를 기준으로 하는 회문은 짝수길이의 회문을 모두 표현하게 된다.