[알고리즘] Manacher 알고리즘 정리 (python)

Manacher 알고리즘

• 회문(Palidnrome)에 관한 문제를 빠르게 풀 수 있도록 만들어주는 알고리즘
• 문자열 S의 부분 문자열 중에서 팰린드롬인 것 중 가장 긴 것의 길이를 구하는 알고리즘을 해결하는 것에 최적화.
• 시간 복잡도 : O(n)

적용 방법

• 문자열 S에 대해 새로운 배열 A를 정의
• 배열 A의 i번째 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기
• Banana를 예시로 들면, S[3]인 문자 a는 자신을 기준으로 an(a)na으로 최대 2의 반지름을 가지므로, A[3] = 2
• 위 방법으로 배열 A을 구성하면 [0, 0, 1, 2, 1, 0]의 값을 얻을 수 있음

문제점

• 어떤 위치(인덱스)를 중심으로 고려하기에 짝수가 아닌 홀수의 회문만 구할 수 있음
• 구한 결과가 회문의 한쪽 길이만 구하기에 결과 숫자가 직관적이지 않을 수 있음

해결 방안

• 각 문자의 앞 뒤에 특수 문자를 끼워 넣어서 해결 가능
• 위 banana의 경우 #b#a#n#a#n#a# 처럼 넣어줌 (특수문자는 #이든, @이든, *이든 상관없음)
• 특수 문자를 끼워 넣은 문자열 S’을 Manacher 알고리즘을 이용해 만든 배열 A’은 [0, 1, 0, 1, 0, 3, 0, 5, 0, 3, 0, 1, 2, 1, 0]으로 만들 수 있음
• 즉 끼워둔 문자에서는 짝수 회문의 길이를, 원래 문자에서는 홀수 회문의 길이를 구할 수 있음

구현 방법

• 사전 정보
  • r → 모든 i의 회문 범위 중 가장 멀리 떨어진 값
  • p → R의 중심점
  • i’ → p를 중심으로 i를 대칭한 점 (2p-i)

1. i ≤ r 여부에 따른 A[i]의 초기값을 설정, i > r인 경우 i가 p의 회문에 속하지 않으니 A[i] = 0
2. i ≤ r 일 경우
   1. A[i’] ≤ r- i 인 경우, i를 기준으로 반지름이 A[i’]인 문자열이 p가 중점인 회문에 속하므로 대칭성을 만족
   2. A[i’] > r + i 인 경우 기존 회문을 벗어나기에 r부터 한 칸씩 늘려가며 탐색하는 과정 필요
   3. 그렇기에 초기값을 min([A[i’], r-i)로 설정 가능

   r, p = 0, 0
   for i in range(N): #
       if i <= r:
           A[i] = min(A[2 * p - i], r - i)
       else:
           A[i] = 0

3. A[i]의 초기값에서부터 S[i-A[i]]과 S[i+A[i]]가 같으면 회문을 형성하므로, A[i]를 증가시키고 아니면 다음 i로 넘어감

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 r < i + A[i]:
	r = i + A[i]
	p = i

 

⚙ 완성된 코드

def manachers(S, N): # N은 문자열 S의 길이
    A = [0] * N 
    r, p = 0, 0
    for i in range(N): #
        if i <= r:
            A[i] = min(A[2 * p - i], r - i)
        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 r < i + A[i]:
            r = i + A[i]
            p = i
    return A