Manacher's algorithm
문자열이 주어지면, 포함된 부분 문자열의 회문(팰린드롬) 여부를 빠르게 찾아내는 알고리즘으로, 각각의 문자(i번째)를 중심으로 하는 가장 긴 팰린드롬의 반지름을 dp테이블에 저장하는 방식으로 구현한다.
이 알고리즘의 경우, 특정 문자를 중심으로 가지는 팰린드롬을 찾기 때문에 문자의 개수가 홀수개인 부분 문자열의 회문 여부만을 찾아낼 수 있는데, 짝수 길이의 부분 문자열의 회문여부도 찾고 싶으면 각 문자 사이에 “#”와 같은 더미 문자를 넣어서 구현하면 된다. 예) 1,2,2,1 -> #,1,#,2,#,2,#,1
O(N)의 시간 복잡도로 부분 문자열의 회문 여부를 찾아낼 수 있다.
각각의 문자를 중심으로 하는 가장 긴 팰린드롬의 반지름을 저장하는 dp테이블을 d라고 하면,
s = [1,2,1,3,1,2,1]의 에서 s[1]=2을 중심으로 하는 가장 긴 팰린드롬은 1,2,1이므로 반지름은 1이다. (중심 제외)
이와 같은 방식으로 dp테이블을 채워보면, d = [0,0,1,3,0,1,0]이다.
j < i인 모든 j에 대하여
left = min(j-d[j]), right = max(j+d[j])
center = (left+right)/2 <- left와 right를 만드는 j
i'은 center을 기준으로 i와 대칭인 점
이라고 하고, 가능한 Case를 분류해 보자.
j 중심으로 하는 팰린드롬의 대칭성을 활용하여 d[i]를 빠르게 찾아낼 수 있는 경우 연산을 스킵하고 dp 테이블을 채우는 것이 이 알고리즘의 핵심이다.
Case1의 경우 대칭성을 온전히 활용할 수 있다.
Case2의 경우 대칭성을 활용할 수 있는 부분은 i~right이고, right~i+d[i]까지는 naive한 방식으로 찾아 내야 한다.
Case3의 경우 대칭성을 활용할 수 있는 부분이 없으므로 전부 naive한 방식으로 구현하여야 한다.
핵심 원리
left ~ right는 j를 중심으로 하는 팰린드롬이고,
i'과 i는 j를 중심으로 대칭이므로, left~i'과 i~right는 j를 중심으로 대칭이다. 따라서 이 안에 포함되는 i’-d[i']~i'과 i~i+d[i]도 대칭이다.
d[i]와 d[i']은 각각 팰린드롬의 반지름을 나타내는 값이고, i와 i'은 팰린드롬의 중심이 되는 값인데, 위의 결과를 바탕으로 중심을 기준으로 양쪽을 생각해 보면, Case 1의 경우 대칭성을 활용하여 d[i]와 d[i']이 같음을 알 수 있다.
# Manacher's Algorithm, O(n)
import sys
n = int(input())
s = list(map(int,sys.stdin.readline().split()))
d = [0 for _ in range(n)]
right = 0; center = 0
for i in range(n):
if i <= right:
d[i] = min(d[2*center-i], right-i)
# min 값을 저장하기 때문에 i+d[i']가 right보다 클 수 없다.
# 조건(i<=right and i+d[i'] <right)을 만족하는 경우에만
# 기존 dp테이블에서 값을 가져오고, 나머지의 경우에는 naive한 방식으로 dp테이블을 채운다.
while (i-d[i] > 0 and i+d[i] < n-1) and (s[i-(d[i]+1)] == s[i+(d[i]+1)]):
d[i] += 1
# ex) i=0,d[i]=0일 경우 d[i]가 1이 되면 안 됨!
# s[i-(d[i]+1)] == s[i+(d[i]+1)]을 미리 확인 해 본 후 d[i]를 1 키워준다
if i + d[i] > right:
right = i + d[i] # right의 최댓값 갱신
center = i # 다음 i부터 적용됨 (j<i)
print(d)
d[i] = min(d[i'], right-i)
만약 d[i'] < right-i라면,
0 <= d[i'] < right-i이므로 i < right이고 i + d[i'] < right이므로 Case1을 만족하므로 d[i] = d[i']
만약 d[i'] > right-i라면,
Case1의 범위를 벗어나게 되지만, i~right까지의 대칭성은 보장하므로
초기 d[i]값을 right-i로 두고 이후의 값은 naive한 방식으로 확인하면 된다.