Manacher 알고리즘 (Manacher's Algorithm)

✅ 팰린드롬(palindrome) 이란?

팰린드롬은 순방향으로 읽었을 때와 역방향으로 읽었을 때 같은 문자열을 의미한다.

문자열	뒤집은 문자열	결과
A	A	palindrome
BB	BB	palindrome
ABDDS	SDDBA	not palindrome
ABDDBA	ABDDBA	palindrome

 

 

🤔 문제: 가장 긴 팰린드롬 부분 문자열(palindrome substring) 찾기

BANANANA 문자열에서 가장 긴 팰린드롬 부분 문자열은 BANANANA 이다.

이렇게 특정 문자열에서 가장 긴 팰린드롬 부분 문자열을 구하려면 어떻게 해야할까?

 

💡 기존 풀이

아마 이 문제가 나오면 문자열의 길이가 O(N^2)의 시간복잡도로 해결할 수 있을 정도로 짧게 주어질 것이다. 그러니 냅다 풀어보자.

 

(1) 팰린드롬의 중심 문자부터 탐색

홀수 길이의 팰린드롬은 중심 문자부터 시작해서 맞은 편의 문자가 서로 일치한다.

홀수 팰린드롬 찾기

4번째 문자인 A가 중심 문자일 때, 양 옆의 포인터를 이동하면서 일치하지 않는 문자가 나올 때까지 탐색하면 된다. 짝수 길이의 팰린드롬 또한 자신과 같은 문자를 옆에 둔 문자를 중심으로 똑같이 탐색하면 된다.

짝수 팰린드롬 찾기

이 작업을 문자열의 길이만큼 반복하므로 시간 복잡도는 O(N^2) 이다.

 

(2) 이전에 구한 팰린드롬 활용 (memorization)

이미 찾은 팰린드롬이 존재할 때, 해당 팰린드롬 양 끝에 같은 문자가 추가되면 새로운 문자열 또한 팰린드롬이 된다.

이를 이용해 이전에 구한 팰린드롬이 있을 때 새로운 팰린드롬을 구할 수 있다.

사실 위 (1) 방법과 똑같으나, 중심이 아닌 팰린드롬의 시작 혹은 끝 문자에서 탐색을 시작할 수 있다. 즉 (1)은 중간에서 시작해서 모든 포인터를 움직이는 투 포인터, (2)는 한 쪽에서 시작해서 하나의 포인터만 움직이는 투 포인터 방식이라고 할 수 있다.

 

이 방식의 경우 이전 연산을 저장하기 위해 추가 메모리가 필요한 대신 (1) 처럼 홀/짝수를 나누지 않아도 되므로 반복문을 한 번만 쓴다. 그래도 시간복잡도는 똑같기 때문에 (1)이 더 효율적이다.

 

 

💡 새로운 풀이: Manacher 알고리즘 (Manacher's Algorithm)

그렇다면 문자열의 길이가 길어서 O(N^2)로는 해결할 수 없는 경우는 어떻게 할까? 바로 Manacher 알고리즘을 사용하면 된다.

 

우선 홀수 팰린드롬만 생각해보자. 

홀수 팰린드롬은 대칭을 이루는 문자열들이 중심 문자의 양 옆에 붙은 형태다. 이 때 중심 문자별로 만들 수 있는 가장 긴 팰린드롬의 반지름 길이(중심 문자~끝 문자)를 계산하는 것이 목표이다. 

 

이를 계산하기 위해서 이전처럼 투 포인터를 움직일 수 있다. 하지만 포인터를 움직이는 시간복잡도 O(N)보다 더 빠른 방법이 필요하다.

 

Manacher 알고리즘은 팰린드롬의 '대칭성'을 이용해 방법을 찾아냈다. 현재 찾아낸 가장 긴 팰린드롬이 있고, 탐색하는 문자가 해당 팰린드롬 내에 존재한다고 생각해보자.

 

• 현재 탐색 문자(화살표가 가리키는 문자): 5번째 문자 'N'
• 현재 가장 긴 팰린드롬: 4번째 문자 'A'가 중심인 'ANANA' 문자열

 

이 때 현재 가장 긴 팰린드롬의 중심 문자를 기준으로, 탐색 문자의 대칭 문자를 구한다. 

• 현재 대칭 문자: 3번째 문자 'N'

 

그리고 현재 가장 긴 팰린드롬의 범위 내에서, 대칭 문자가 중심인 가장 긴 팰린드롬을 이용해 현재 탐색 문자를 중심으로 하는 팰린드롬을 알 수 있다. 왜? 현재 가장 긴 팰린드롬 내에서는 대칭성이 보장되기 때문이다. 

물론 이는 현재 가장 긴 팰린드롬의 범위 내에서만 유효하므로, 밖에서 더 긴 팰린드롬이 있는 지 추가적인 탐색이 필요하다. 하지만 투 포인터 시작 위치가 달라졌기 때문에 불필요한 탐색을 줄였다.

 

위 상황을 일반화하면 다음과 같이 나타낼 수 있다.

출처: https://cp-algorithms.com/string/manacher.html

 

전체 코드 또한 아래와 같다.

def manacher(string: str) -> str:
    max_rounds = [0 for _ in range(len(string))]
    center, outbound = 0, 0
    longest_palindrome = string[0]

    for curr in range(len(string)):
        r = 0

        # 대칭 문자를 통한 최적화 가능
        if curr <= outbound:
            oppo = center * 2 - curr # 대칭 문자 위치
            r = min(outbound - curr, max_rounds[oppo])

        # 최장 팰린드롬 구하기
        while curr - r >= 0 and curr + r < len(string):
            if string[curr - r] != string[curr + r]:
                break
            r += 1
        r -= 1 # 범위 밖이어야 위 while 문이 종료되어 범위에 맞춤

        max_rounds[curr] = r
        if outbound < curr + r:
            outbound = curr + r
            center = curr

        if r * 2 + 1 > len(longest_palindrome):
            longest_palindrome = string[curr - r: curr + r + 1]

    return longest_palindrome

 

시간 복잡도가 O(N)?

각 문자를 중심으로 하는 가장 긴 팰린드롬을 탐색할 때 최적화가 일어났다. 하지만 여전히 최악의 경우 전체 문자열을 탐색해야 한다. 그러면 여전히 O(N^2) 아닌가?

 

위 알고리즘을 다시 떠올려보면, 현재 탐색 시작 위치를 정할 때 대칭 문자의 가장 긴 팰린드롬을 참고한다. 가장 긴 팰린드롬의 길이는 탐색이 진행될 때마다 감소하지 않으며 최대 N 까지 가능하다. 따라서 O(N + N) = O(N) 이라 할 수 있다.

 

 

짝수 길이의 팰린드롬?

중심 문자가 2개인 짝수 팰린드롬은 해당 알고리즘으로 구할 수 없다. 따라서 살짝 꼼수가 필요한데, 문자열의 각 문자들 사이에 더미 문자를 삽입하는 것이다.

이러면 중심 문자가 더미 문자일 때 짝수 팰린드롬을, 일반 문자일 때 홀수 팰린드롬을 구할 수 있다.