Manacher's Algorithm [가장 긴 펠렌드롬 찾기]

안녕하세요. gaki 입니다. 오늘은 가장 긴 펠렌드롬을 O(N) 의 시간복잡도로 찾을 수 있는 Manacher's 알고리즘에 대해서 이야기 해보겠습니다.

 

<목차>

1. O(N^2) 으로 가장 긴 펠렌드롬 찾는 방법

2. Manacher's 알고리즘의 접근 방법 

3. LeetCode 문제풀이

 

---

1. O(N^2) 으로 가장 긴 펠린드롬을 찾는 방법

먼저 Manacher's 알고리즘에 대해서 알아보기 전에, 이 알고리즘이 왜 유용한지에 대해서 설명해보겠습니다.

 

babad

위와 같은 문자열이 있다고 가정해봅시다.

이 문자열에서 가장 긴 펠렌드롬을 찾으려면 어떻게 해야할까요?

아니, 그 전에 펠렌드롬이 뭔지 알아야겠죠?

 

펠렌드롬은 거꾸로 뒤집어도 원래의 문자열과 같은 문자열을 의미합니다.

가령, ABBCBBA 라는 문자열은 거꾸로 뒤집어도 ABBCBBA 이므로, 펠렌드롬입니다.

AVCA 는 거꾸로 뒤집으면 ACVA 이고, 원래의 문자열과 다르므로 펠렌드롬이 아닙니다.

 

그럼 다시 주제로 돌아와서, babad 라는 문자열에서 가장 긴 펠렌드롬은 무엇일까요?

직관적으로 bab 나, aba 임을 알 수 있습니다.

이 문자열들보다 더 긴 펠렌드롬은 찾을 수 없기 때문이죠.

 

이것을 직관적으로 코드로 구현하면 다음과 같습니다.

def isPalindrome(string):
	
    n = len(string)
    ret = ""
    
    for i in range(n):
    	for k in range(i, n):
        	 nowString = string[i:k+1]
             
             if (nowString == nowString[::-1]):
             	ret = max(ret, nowString, key=lambda x: len(x))
    return ret

 

완전탐색으로 모든 경우의수를 탐색하는 방법입니다.

이때 시간복잡도는 O(N^2 *M) 입니다.

위의 코드 보다 약간 더 시간을 단축시킬수 있는 방법의 코드는 아래의 코드입니다.

 4 def isPalindrome(string):
  5     n = len(string);
  6     ret = ""
  7
  8     def search(a,b):
  9         while (a >= 0 and b < n and string[a] == string[b]):
 10             a -= 1
 11             b += 1
 12         return string[a+1:b]
 13
 14
 15     for i in range(n):
 16         first = search(i,i+1)
 17         second = search(i,i)
 18         ret = max(ret, first, second, key=lambda x:len(x))
 19     return ret

다이나믹 프로그래밍을 활용해서 첫 시작점 둘을 지정하고, 확장시켜가는 방법입니다.

위 코드의 시간복잡도는 O(N^2) 입니다.

 

 

하지만, 여기서 더 빠르게 펠린드롬을 찾을 수 있는 방법이 있습니다.

바로 오늘 소개해드리려는 Manacher's algorithm 입니다.

 

---

2. Manacher's 알고리즘의 접근 방법

 

Manacher's 알고리즘은 O(N) 의 시간복잡도로 문자열이 펠린드롬인지 확인하는 알고리즘입니다.

이를 구현하기 위해서 알아야할 선행지식이 하나 있는데,

그것은 펠린드롬의 대칭성입니다.

 

                                     

                                      A   B   A   B   C   B   A   B   A

펠린드롬의 반지름          0    1   1    0   4   0   1    1    0                   

 

위와 같은 문자열 ABABCBABA 가 있다고 하면, 중심이 C 일때 가장 긴 반지름의 펠린드롬이 만들어집니다.

그리고 C 를 중심으로 좌우의 문자들은 대칭이기 때문에, 좌측의 문자의 펠린드롬 반지름이 우측 문자의 펠린드롬 반지름과 일치합니다.

이 아이디어를 바탕으로 우리는 펠린드롬 알고리즘을 사용할 수 있습니다.

 

이제, 몇개의 변수를 선언할 것입니다.

 

먼저 p 라는 변수는 가장 먼 곳까지 보고있는 문자열의 인덱스입니다.

R 이라는 변수는 현재 볼 수 있는 가장 먼 곳의 인덱스입니다.

마지막으로 A[] 라는 배열은, 펠린드롬의 반지름을 담고있는 배열입니다.

 

기본적으로 펠린드롬 알고리즘은 문자열의 왼쪽서부터 오른쪽으로 진행하며, 순차적으로 문자열을 탐색합니다.

그리고 현재 탐색하고 있는 문자의 인덱스가 R 값보다 작다면, (그러니깐, 현재 볼 수 있는 가장 먼 곳의 인덱스 값보다 작다면.)

현재 탐색하고 있는 문자의 A[] 값은 대칭인 구간의 A[] 값보다 크거나 같다고 볼 수 있습니다.

그 이후, 좌우로 펼쳐가면서 펠린드롬인 지점까지 탐색해준다음, 그 값에 따라 R 과 p 를 갱신해줍니다.

 

제가 그랬다시피, 이 글을 읽고 있으신 독자분들은 아마 아직까지 잘 이해가 안될것이기 때문에, 다시한번 요약해보겠습니다.

 

이 Manacher's 알고리즘을 제대로 이해하려면, 각 변수가 가진 의미를 제대로 아는것이 가장 중요합니다.

 

R 은 가장 멀리 볼 수 있는 인덱스의 값입니다.

 

가령, A B B A C A B B A 라는 값이 있다고 해봅시다.

아까 말했다시피 펠린드롬은 왼쪽에서 오른쪽으로 문자열을 탐색하며 진행합니다.

 

먼저 맨 처음 문자인 A 에 도달했습니다.

참고로, p 와 R 의 초기값은 -1 입니다.

 

A 의 인덱스는 0 입니다.

현재 R 의 값은 -1 입니다.

R 의 값이 -1이라는 것의 의미는, 현재 가장 멀리 볼 수 있는 위치의 인덱스가 -1 이라는 뜻입니다. 즉, 아직 아무것도 볼수가 없다는거죠.

A 의 인덱스가 R 의 인덱스보다 크므로, 현재 위치인 A 에서의 가장 긴 펠린드롬 반지름은 0 입니다.

또한 현재 위치인 A 에서의 가장 긴 펠린드롬 반지름 + 현재의 인덱스가  R 보다 크다면, R 과 p 값을 갱신해줍니다.

 

현재 A 에서, 가장 멀리 볼 수 있는 인덱스는 A 자기 자신입니다. 따라서 R 은 0 입니다.

이에 해당하는 중심점의 위치는 마찬가지로 A 이기때문에, p 도 0 이됩니다.

 

다음 B 로 가봅시다.

B 의 인덱스는 1 입니다.

B 의 가장 긴 펠린드롬 반지름은 0 입니다.

이때 R 의 값은 어떻게 바뀌어야할까요?

아까 말했듯 R 은 현재 볼 수 있는 가장 먼 거리의 인덱스라고 했습니다.

현재 볼 수 있는 가장 먼 거리의 인덱스는 바로 B 자기자신이므로, R 은 1로 갱신해주어야합니다.

그에따라 p 도 1 이 되겠죠?

 

다음 B 로 가봅시다.

B 의 인덱스는 2입니다.

B 위치에서 가장 긴 펠린드롬 반지름은 0 입니다. (왜냐하면 B 를 중심으로 보았을때 왼쪽에서는 B, 오른쪽에는 A 가 있기 때문이죠.)

이때 R 의 값은 2 로 바뀌어야합니다.

가장 멀리 볼 수 있는 인덱스는 바로 B 자기자신이기떄문이죠.

따라서 p 도 2 로 바뀌어야합니다.

 

다음 A 로 가봅시다.

A의 인덱스는 3 입니다.

A 의 위치에서 가장 긴 펠린드롬 반지름도 마찬가지로 0 입니다.

이떄 R 의 값은 3 으로 바뀌어야합니다.

가장 멀리 볼 수 있는 인덱스는 바로 B 자기자신이기떄문이죠.

따라서 p 도 3 로 바뀌어야합니다.

 

다음 C 로 가봅시다.

C 의 인덱스는 4 입니다.

C 의 위치에서 가장 긴 펠린드롬 반지름은 4 입니다! (왜냐면 C 를 중심으로 각각 4개씩 문자가 대칭이기 때문이죠)

그럼 R 은 어떻게 바뀌어야할까요?!

계속 강조헀다시피 R 은 가장 멀리 보고있는 인덱스라고했습니다.

현재 C 의 위치에서 가장 긴 펠린드롬의 반지름은 4 이며, 이때 탐색을 하면서 A B B A C A B B A  모든 문자열을 다 탐색했습니다.

즉, 현재 가장 멀리 볼 수 있는 인덱스는, 마지막 A 입니다!

따라서 R 은 마지막 A 의 인덱스인 8이 되어야 합니다.

또한 R 에 해당하는 중심의 위치이므로, 현재 C 의 인덱스인 4 가 되어야합니다.

 

다음 A 로 가봅시다.

A 의 인덱스는 5 입니다.

위에서 R 의 값은 8 로 만들어주었습니다.

즉, 가장 멀리 보고 있는 인덱스가 8인데, 5는 8보다 작으므로, 이미 한번 봤었던 문자라는 의미입니다.

 

따라서, 이때 펠린드롬의 대칭성을 사용할 수 있습니다.

2 * p - 현재 인덱스 를 하게되면, 2 * 4 - 5 = 3 이 됩니다.

즉 3 번쨰 인덱스의 문자가 현재 5번쨰 인덱스의 A 와 대칭의 위치에 있다는 뜻입니다.

 

즉 A 의 가장 긴 펠린드롬은 일단 0 입니다. ( 왜냐하면 3번째 인덱스인 A 의 가장 긴 펠린드롬도 0 이였기 때문)

그 이후, A 의 좌우측을 넓혀가면서 탐색해보면 현재 위치인 5번쨰 인덱스 A 의 펠린드롬반지름은 0 임을 알 수 있습니다.

 

이런식으로 쭉쭉 진행하다보면 모든 위치에서의 가장 긴 펠린드롬 반지름을 구 할 수 있게됩니다.

 

이 알고리즘의 특징은 R 의 값이 현재 문자의 인덱스보다 클 때, 이미 기존에 한번 탐색했던 범위에 포함되므로, 펠린드롬의 대칭성을 이용하여 중복되는 곳의 계산을 배재할 수 있다는 것이 특징입니다.

 

이 알고리즘을 이해하는 가장 좋은 방법은 코드를 보고, 코드의 진행을 순서대로 종이에 옮겨적으면서 이해해보는것 입니다.

제가 설명드린 방법으로 코드를 짜다보면 한가지 문제가 생기는데, 그것은 문자열의 개수가 홀수일때만 적용된다는 것입니다.

이를 해결하기 위해서 문자열 앞뒤와 중간에 임의의 문자인 "#" 을 추가해, 그 상태로 펠린드롬 함수를 돌리면 정답을 얻을 수 있습니다.

 

---

3. Manacher's 알고리즘 실습

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

class Solution:
    def longestPalindrome(self, s: str) -> str:
        S = str
        n = len(S)
        
        R = -1 # 가장 멀리 볼 수 있는 곳의 인덱스
        p = -1 # 가장 멀리 볼 수 있는 곳을 만들어준 곳의 위치
        A = [0] * n # 가장 긴 펠린드롬 반지름을 담은 배열
        ret = ""
        
        for i in range(n):
           	if (R > i):
            # 현재 위치가 R 보다 작다는것은, 이미 한번 탐색했던 이력이 있다는 뜻이다. 
            # 따라서 펠린드롬상의 대칭인 지점의 펠린드롬 반지름값으로 값을 만들 수 있다.
                A[i] = min(A[2*p - i], R-i)
            else:
                A[i] = 0
            
            while (i-A[i]-1 >= 0 and i+A[i]+1 < n and S[i - A[i] - 1] == S[i + A[i] + 1]):
                A[i] += 1
            
            if (i + A[i] > R):
                R = i + A[i]
                p = i
        
        maxV = -1;
        maxI = -1
      
        for i in range(n):
            if (maxV < A[i]):
                maxV = A[i]
                maxI = i
        
        return S[maxI - maxV: maxI + maxV + 1]

위의 코드는 문자열이 홀수일 경우에만 적용되는 펠린드롬 판별법입니다.

위에서 설명한 내용의 핵심만을 담아놓은 코드죠.

 

만약에 홀수, 짝수 모든  경우를 탐색하고 싶으면,

아래코드를 사용하시면 됩니다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        S = "#" + "#".join(s) + "#"
        n = len(S)
        
        R = -1
        p = -1
        A = [0] * n
        ret = ""
        
        for i in range(n):
            if (R > i):
                A[i] = min(A[2*p - i], R-i)
            else:
                A[i] = 0
            
            while (i-A[i]-1 >= 0 and i+A[i]+1 < n and S[i - A[i] - 1] == S[i + A[i] + 1]):
                A[i] += 1
            
            if (i + A[i] > R):
                R = i + A[i]
                p = i
        
        maxV = -1;
        maxI = -1
      
        for i in range(n):
            if (maxV < A[i]):
                maxV = A[i]
                maxI = i
        
        return S[maxI - maxV: maxI + maxV + 1].replace("#", "")

---

Reference

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

Manacher's Algorithm - Linear Time Longest Palindromic Substring - Part 1 - GeeksforGeeks