Manacher's Algorithm

많은 분이 Palindromic Substring을 찾는 문제 해결 방법을 찾다 Manacher's Algorithm을 알게 됐을텐데, 해당 알고리즘을 알아보겠습니다.
Palindrome(회문)이란 순서를 뒤집어도 똑같은 문장 혹은 단어를 의미합니다. race car, noon, 기러기, 다시 합창합시다 등 거꾸로 읽어도 동일한 의미를 가집니다.

Core Algorithm

해당 알고리즘은 반복문을 돌며 해당 위치의 문자를 중심으로 Palindrome이 되는지 검사합니다.

Brute Force로 생각하면 매 문자를 기준으로 Palindrome이 만족하는지를 반복 검사하면 됩니다.
Manacher's Algorithm은 이전에 검사한 Palindrome을 이용해 새로운 Palindrome을 찾는 DP(Dynamic Programming)로 접근합니다.

이를 수행하기 위한 방법인 Mirror Optimization 즉, 대칭점 최적화가 있습니다.
Palindrome 특징은 중심을 기준으로 반드시 대칭을 이루는데, 이 특징을 이용하여 이전 Palindrome의 길이를 구해 해당 길이부터 새로운 Palindrome을 찾습니다.

중점 c를 기준으로 aba, aba가 대칭을 이루는 것을 볼 수 있습니다.

위 대칭점을 찾을 때 반드시 최적화 과정이 필요한데, 왜 최적화 과정이 필요한지 알아보겠습니다.

Algorithm 조건 1

대칭점을 찾기 전, 필요한 변수는 총 3개 입니다.

Palindrome의 중심값 Center
Palindrome의 오른쪽 끝 위치값 Right
i번째 Palindrome의 길이를 저장하는 P 리스트 (C부터 R의 반지름 크기 저장)

이후 i번째 인덱스의 대칭점(mirror)을 찾기 위해 mirror = C*2-i 공식을 이용해 대칭점을 찾고 이를 최적화합니다.
결론적으로 이와 같은 수식이 나오는데 P[i] = min(R-i, P[mirror]) 그 이유를 알아보겠습니다.

대칭점 최적화를 진행하는 이유는 아래 3가지 조건을 만족시키기 위함입니다.

기존 Palindrome 영역에 포함되는 경우
기존 Palindrome 영역 경계에 맞닿아 범위를 초과하는 경우
기존 Palindrome 영역을 벗어난 경우

대칭점 조건 1 (Palindrome 영역에 포함되는 경우)

1번 경우를 수식으로 나타내면 P[mirror] < R-i입니다.(대칭점이 기존 Palindrome 영역 안에 존재)

mirror = C*2-i → 5*2-6 = 4 → P[4(mirror)] = 0
P[mirror] < R-i → 0 < 2(8-6) 조건 만족
위 조건을 만족하는, 즉 Palindrome 범위 안에 대칭점이 있는 경우 P[i] = P[mirror] 사용

P[i] = P[mirror]을 사용한다는 의미는 P[i]의 새로운 Palindrome을 찾을 때 이전 P[mirror]에 존재하는 Palindrome 값을 재활용한다는 의미입니다.(자세한 내용은 아래 How to Work 참고)

대칭점 조건 2 (Palindrome 영역 경계에 맞닿아 범위를 초과하는 경우)

2번 경우를 수식으로 나타내면 P[mirror] ≥ R-i입니다. (대칭점이 기존 Palindrome 영역을 벗어날 수 있음)

Manacher's Algorithm의 접근 방법은 Palindrome의 대칭성을 이용하여, 이전 Palindrome에서 구한 값을 재계산하지 않고 재활용하겠다는 의미입니다.
하지만 기존 Palindrome을 벗어나는 범위가 생기면 "범위가 벗어난 곳은 Palindrome이다"를 보장할 수 없습니다.

mirror = C*2-i → 7*2-9 = 5 → P[5(mirror)] = 3
P[mirror] ≥ R-i → 3 ≥ 2(11-9) 조건 만족
위 조건을 만족하는, 즉 Palindrome 범위 안에 대칭점이 있는 경우 P[i] = P[mirror] 사용한다면
P[i] = 3이 되어 현재 index 9를 기준으로 앞뒤 3까지는 Palindrome으로 이해

실제 3~11 Palindrome 인덱스 범위를 벗어난 인덱스 12도 Palindrome으로 봐버리는 오류 발생
이를 해결하기 위해 P[mirror] ≥ R-i 조건에선 Palindrome을 보장할 수 있는 범위까지만 대칭점의 값을 사용

mirror = C*2-i → 7*2-9 = 5 → P[5(mirror)] = 3
P[mirror] ≥ R-i → 3 ≥ 2(11-9) 조건 만족
P[i] = R-i → 2

3~11 Palindrome을 보장할 수 있는 범위내에서만 대칭점의 값을 사용하여 7~11까지 Palindrome을 보장하고 이후 Palindrome 탐색

대칭점 조건 3 (Palindrome 영역을 벗어난 경우)

3번 경우를 수식으로 나타내면 i ≥ R입니다. (기존 Palindrome 영역을 벗어난 영역)

Palindrome을 보장할 수 있는 범위내에서만 대칭점의 값을 사용하기 때문에 영역을 벗어난 경우 P[i]=0으로 초기화합니다.

(추가적으로) i ≥ R 조건에 대해 i == R이면 위 조건2에 해당합니다.(i==R이면 P[mirror] ≥ R-i는 항상 참)
그럼에도 ≥ 조건을 쓰는 이유는 코드 레벨에서 조건2의 항상 참인 부분을 굳이 계산하지 않고 i ≥ R 조건으로 P[i] = 0으로 초기화합니다.

위 조건 3가지에 따라 대칭점을 P[i] = P[mirror] or R-i or 0을 넣어야 합니다.
이를 코드레벨에서 최적화하면 P[i] = (i < R) ? min(R-i, P[mirror]) : 0이 됩니다.

Algorithm 조건 2

새로운 Palindrome을 갱신한다는 의미는 C와 R을 갱신한다는 의미이며, 이는 i+P[i] > R이라는 의미입니다.
i(현재 인덱스) + P[i](대칭점+새로운 Palindrome 추가 길이)가 R(기존 Palindrome 길이)을 벗어나 새로운 Palindrome을 갱신합니다.
이를 식으로 표현하면 if i+P[i] > R then C = i, R = i + P[i]

이제 구체적인 동작 과정을 알아보겠습니다.

How to Work

초기 P[]는 0으로 초기화하고, C, R도 0으로 초기화합니다.
@, $는 밑에서 다시 설명하겠습니다.

1번 인덱스(i=1)를 기준으로 i ≥ R 조건이 됩니다. (알고리즘 조건1 - 대칭점 조건3)

i=1 ≥ R=0(초기화 0으로 진행)이므로 P[i] = 0으로 초기화, 유효한 Palindrome은 없어(@ != a) 확장 불가

i+P[i] > R(알고리즘 조건2)이므로 C, R 갱신합니다.

i+P[i]=1+0=1 > R=0 → C=1(C=i), R=1(R=i+P[i])로 갱신

2번 인덱스(i=2)를 기준으로 i ≥ R 조건이 됩니다. (알고리즘 조건1 - 대칭점 조건3)

i=2 ≥ R=1이므로 P[i] = 0으로 초기화하고, 유효한 Palindrome은 없어(a != b) 확장 불가

i+P[i] > R(알고리즘 조건2)이므로 C, R 갱신합니다.

i+P[i]=2+0=2 > R=1 → C=2(C=i), R=2(R=i+P[i])로 갱신

3번 인덱스(i=3)를 기준으로 i ≥ R 조건이 됩니다. (알고리즘 조건1 - 대칭점 조건3)

i=3 ≥ R=2이므로 P[i] = 0으로 초기화하고, 유효한 Palindrome이 존재
(a == a), (a != c)로 1개 확장 가능하므로 기존 초기화된 P[i]에 +1 증가하여 P[i]=1

i+P[i] > R(알고리즘 조건2)이므로 C, R 갱신합니다.

i+P[i]=3+1=4 > R=2 → C=3(C=i), R=4(R=i+P[i])로 갱신
P[3]=1(1개 확장된 Palindrome), 1은 반지름을 의미하며 Palindrome이 2~4번 인덱스 범위를 뜻

4번 인덱스(i=4)를 기준으로 i ≥ R 조건이 됩니다. (알고리즘 조건1 - 대칭점 조건3)

i=4 ≥ R=4이므로 P[i] = 0으로 초기화하고, 유효한 Palindrome은 없어(b != c) 확장 불가

i+P[i] > R(알고리즘 조건2)이 안되므로 C, R 갱신하지 않습니다.

i+P[i]=4+0=4 > R=4 → 조건 만족 X라서 C,R 갱신 X

5번 인덱스(i=5)를 기준으로 i ≥ R 조건이 됩니다. (알고리즘 조건1 - 대칭점 조건3)

i=5 ≥ R=4이므로 P[i] = 0으로 초기화하고, 유효한 Palindrome이 존재
(a == a), (b == b), (a == a), (a != c)로 3개 확장 가능하므로 기존 초기화된 P[i]에 +3 증가하여 P[i]=3

i+P[i] > R(알고리즘 조건2)이므로 C, R 갱신합니다.

i+P[i]=5+3=8 > R=4 → C=5(C=i), R=8(R=i+P[i])로 갱신
P[5]=3(3개 확장된 Palindrome), 3은 반지름을 의미하며 Palindrome이 2~8번 인덱스 범위를 뜻

6번 인덱스(i=6)를 기준으로 i ≥ R 조건이 안되고, P[mirror] < R-i 조건이 됩니다. (알고리즘 조건1 - 대칭점 조건1)

i=6 ≥ R=8이므로 조건 만족 X
mirror = 2*C(5)-i(6) → 4 이므로 P[4(mirror)]=0 < 3(R-i) 조건 만족
P[i] = P[mirror] → P[i]=0이므로 P[i] = 0으로 초기화
유효한 Palindrome은 없어(c != b) 확장 불가

i+P[i] > R(알고리즘 조건2)이 안되므로 C, R 갱신하지 않습니다.

i+P[i]=6+0=6 > R=8 → 조건 만족 X라서, C,R 갱신 X