전체 문자열에서 palindrome의 갯수 세기; O(N)

2015. 6. 10. 02:19알고리즘 문제풀기/문자열

Manacher, Glenn이 1975년에 발표한 논문에 실렸던 알고리즘이다.
전체 문자열의 부분 문자열에서 palindrome의 갯수를 세고 그 위치 또한 알 수 있다.

먼저 문자 사이사이에 # 등을 삽입한다. 이렇게 하면 palindrome의 홀짝(aba, abba)을 따질 필요가 없기 때문이다.
abacada를 #a#b#a#c#a#d#a# 로 바꾸는것.
알고리즘은 현재까지 찾은 palindrome 중 right bound(오른쪽 끝)이 가장 오른쪽에 있는 palindrome을 저장하며 진행한다.
또한 dp table을 채워나가는데, dp[i]는 i번째 문자를 기준으로 하는 가장 긴 palindrome의 길이의 절반이다.

예)

abacada:

#

a

#

 b

 #

 a

 #

 c

 #

a

 #

 d

#

a

 #

 0

1

0

3

0

 1

0

 3

0

1

0

3

0

1

0


dp[i]를 채우려고 한다고 하자.

1) 가장 긴 palindrome에 i번째 문자가 포함된다고 하자. 가장 긴 palindrome을 '검은 것'으로 표현하겠다.

그에 대칭적인 위치에 문자가 있을 것이다.
그 문자의 dp값은 이미 채워져 있을 것이다.



경우를 나눌 수 있다.

첫 번째는 그 문자를 중심으로 하는 가장 긴 palindrome이, 검은 것의  경계 안에 있을 경우이다.
이 경우 i의 dp값은 대칭되는 위치의 dp값과 같다.
그만큼은 대칭이기 때문에 보장되어있고, 그보다 더 길다면 dp값이 그만큼 커졌어야 하기 때문이다.
이 때 경계에 딱 걸치는 경우에는 설명이 불가능하다.

두 번째 경우를 설명하는 다음 그림을 보자.


이 경우, 검은색이 가장 긴 palindrome이므로, 1번 위치와 4번 위치의 문자는 다르다.
하늘색이 palindrome이므로, 1과 2가 같고, 검은색이 palindrome이므로 2와 3또한 같다.
따라서 3과 4가 다르고, i에서 가장 긴 palindrome은 검은 색의 경계를 넘어가지 못한다는 것을 알 수 있다.

두 경우 모두 dp[i]를 O(1)만에 구하는 것이 가능했다. 여기서 right bound가 가장 오른쪽에 있는 palindrome은 변하지 않았다.

2) 가장 긴 palindrome에 i번째 문자가 포함되지 않는 경우이다. 이 경우 i는 검은색의 right bound의 오른쪽에 있다. i를 중심으로 양쪽으로 '뻗어나가며' 가장 긴 palindrome을 찾아 dp[i]에 기록해두고, 검은색을 i로 대체하면 된다.


1)은 최대 O(N)번 반복되며 각각 시간복잡도가 O(1)이므로 O(N)이다.

2)는, right bound는 항상 증가한다는 사실에서 모든 (2)의 시간복잡도를 합하면 O(N)임을 알 수 있다.