마나커(Manacher) 알고리즘

1. 마나커 알고리즘(Manacher's Algorithm)이란?

어떤 문자열에서 팰린드롬의 개수와 위치를 찾는 알고리즘이다.

 

팰린드롬이란?
팰린드롬(회문, Palindrome)은 전체 문자열을 뒤집었을 때 원래 상태와 같은 수열, 문자열 등을 의미한다.
ex) "기러기", "eye", "level", "aba", "aa"

 

 

마나커 알고리즘은 문자열 길이의 P 배열에 i번째 문자를 중심으로 한느 가장 긴 팰린드롬의 반지름 크기를 저장한다.

시간복잡도는 O(N)으로 접미사배열 + LCP 배열을 이용한 방법 O(NLogN)보다 빠르다.

 

https://small-stepping.tistory.com/936

멘버 마이어스 알고리즘과 Kasai 알고리즘

 

진행방식은 다음과 같다.

1. i는 0부터 N - 1 (N = 문자열 길이)까지 진행한다.
2. j < i인 모든 j에 대해 r = maxOf(r, j + P[j])를 구하고, 이 j를 c라고 칭한다. r = c + P[c] (c = center, r = radius)
3. if (r < i) { P[i] = 0 } else { P[i] = minOf(P[2 * c - i], r - i) }
4. S[i - P[i]] == S[i + P[i]]일 때까지 P[i]를 1씩 증가시킨다.

 

3번의 if (r < i) P[i] = 0 else P[i] = minOf(P[2 * c - i), r - i)

r < i 일 경우, i번째 문자가 i 미만의 문자를 중심으로 하는 팰린드롬의 범위 밖에 위치한다는 것이다.

예를 들어 "cabadak" 라는 문자열이 있을 때, s[4]는 d이다.

이 s[4]는 팰린드롬 "aba"에 속하지 않는다. aba에 속하는 것은 s[1] .. s[3]의 범위이다.

 

이런 경우 이전 index에서 얻은 정보를 재활용할 수 없으므로 초기값이 기준점 i양 옆으로 1씩 이동하며 비교하여 팰린드롬을 확장하는 것이다.

 

r >= i 일 경우, 이는 i번째 문자가 i미만의 문자를 중심으로 하는 팰린드롬에 속한다는 것이다.

 

예를 들어, "cababad"라는 문자열이 있을 때, s[4]는 팰린드롬 "ababa"에 속한다.

이럴 경우 3가지 상황이 발생할 수 있는데 이에 따라 P[i]의 초기값이 달라진다.

 

 

• i를 중심으로 하는 가장 긴 팰린드롬이 j < i인 j를 중심으로 하는 가장 긴 팰린드롬에 완전히 포함되는 경우

 

j를 기준점으로 잡았을 때, i의 대칭점을 i`라고 하자.

i를 기준으로 하는 가장 긴 팰린드롬과 i`를 기준으로 하는 가장 긴 팰린드롬은 대칭이다.

 

따라서 P[i] = P[i`]이고, P[i`]는 이미 이전에 구했기에 더 이상의 연산은 필요하지 않다.

두 팰린드롬은 j기준으로 양 옆으로 P[j]만큼 대칭이 보장되기 때문에 대칭일 수 밖에 없다.

 

 

• i를 중심으로 하는 가장 긴 팰린드롬이 j < i인 j를 중심으로 하는 가장 긴 팰린드롬에 일부만 포함되는 경우

 

j를 기준점으로 잡았을 때, i의 대칭점을 i`라고 하자.

i를 기준으로 하는 가장 긴 팰린드롬과 i`를 기준으로 하는 가장 긴 팰린드롬은 대칭은 아니지만,

 

 

j를 기준으로 하는 가장 긴 팰린드롬 구간에 포함되는 i, i`를 기준으로 하는 팰린드롬은 대칭이 보장된다.

따라서 i기준 양 옆으로 (j + P[j]) - i + 1부터 비교하면 된다.

 

초기값은 P[i] = (j + P[j]) - i가 되고, 양 옆으로 1씩 이동하면서 비교하면 된다.

 

 

• i를 중심으로 하는 가장 긴 팰린드롬이 j < i인 j를 중심으로 하는 가장 긴 팰린드롬과 겹치는 경우

 

j를 기준점으로 잡았을 때, i의 대칭점을 i`라고 하자.

i를 기준점으로 하는 가장 긴 팰린드롬과 i`를 기준으로 하는 가장 긴 팰린드롬은 대칭인지 아닌지 알 수 없다.

 

 

 

하지만 이 경우 또한 2번 케이스처럼 j를 기준으로 하는 가장 긴 팰린드롬 구간에 포함되는 i, i`를 기준으로 하는 팰림드롬은 대칭이 보장된다.

 

따라서 2번 케이스처럼 초기값은  P[i] = (j + P[j]) - i가 되고, 양 옆으로 1씩 이동하며 비교하면 된다.

 

 

이 전제를 가지고 문자열 "abcabacxyac"의 동작과정을 살펴보자

 

index = 0

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0
r	0
c	0

 

P[i]: i번째 문자를 중심으로 하는 가장 긴 팰린드롬의 반지름 크기
r: i - 1 단계까지의 모든 팰린드롬의 끝나는 인덱스 중에 가장 큰 값
c: i - 1 단계까지 r의 값이 최대가 되게 하는 중심 인덱스를 저장

 

 

index = 1

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0	0
r	0	1
c	0	1

 

바로 이전 단계(index = 0)에 저장된 r, c의 값은 모두 0. (j < i인 j 중에 j + A[j]가 최대가 되는 경우는 j + A[j] = 0, j = 0이다.)

 

r < i 이므로 P[i] = 0

i에서 (P[i] + 1) 이상으로 팰린드롬 확장이 불가능하다. 따라서 P[i] = 0으로 변함이 없다.

r < i + P[i]이므로 r, c의 값 각각 r = 1, c = 1로 갱신한다.

 

 

index = 2

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0	0	0
r	0	1	2
c	0	1	2

 

이전 r = 1, c = 1

 

r < i 이므로 P[i] = 0

여전히 팰린드롬 확장은 불가능하므로 P[i] = 0

r < i + P[i]이므로 r = 2, c = 2

 

 

index = 3

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0	0	0	0
r	0	1	2	3
c	0	1	2	3

 

이전 r = 2, c = 2

 

r < i 이므로 P[i] = 0

여전히 팰린드롬 확장은 불가능하므로 P[i] = 0

r < i + P[i]이므로 r = 3, c = 3

 

 

index = 4

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0	0	0	0	2
r	0	1	2	3	6
c	0	1	2	3	4

 

이전 r = 3, c = 3

 

r < i 이므로 P[i] = 0

i에서 (P[i] + 1) 이상으로 팰린드롬 확장이 가능하다. 양 옆으로 최대 2칸("cabac") 늘리고, P[i] = 2가 된다.

r < i + P[i] 이므로 r = 6, c = 4

 

 

index = 5

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0	0	0	0	2	0
r	0	1	2	3	6	6
c	0	1	2	3	4	4

 

이전 r = 6, c = 4

 

r >= i 이므로 P[i] = minOf(P[2 * c - i], r - i) = minOf(P[2 * 4 - 5], 6 - 5) = minOf(P[3], 1) = minOf(0, 1) = 0

팰린드롬 확장이 불가능하므로 P[i] = 0

r >= i + P[i] 이므로 r, c 값은 갱신하지 않는다.

 

이 단계는 위에서 말한 3가지 상황 중 1번 케이스에 해당하는 항목이다.

index 4를 기준점으로 잡았을때 대칭점인 index 3과 index 5를 기준으로 하는 팰린드롬은 대칭이다.

P[i] = P[i`] 이므로, i` = 2 * c - i, P[i] = P[2 * c - i]가 된다.

 

 

index = 10

Index String	0 a	1 b	2 c	3 a	4 b	5 a	6 c	7 x	8 y	9 a	10 c
P	0	0	0	0	2	0	0	0	0	0	0
r	0	1	2	3	6	6	6	7	8	9	10
c	0	1	2	3	4	4	4	7	8	9	10

 

위 과정을 반복하여 배열 P를 채운다.

P[2] = 0, 양 옆으로 최대 0만큼 확장이 가능하므로 팰린드롬 최대 길이는 1이다.

P[4] = 2, 양 옆으로 최대 2만큼 확장이 가능하므로 팰린드롬 최대 길이는 5이다.

문자열 "abcabacxyac"에서의 가장 긴 팰린드롬 부분 문자열의 길이는 5이다.

 

 

짝수 팰린드롬이 있는 경우 처리 방법

위 방식대로 진행할 경우 예외 상황이 발생한다.

문자열 "xyzzzzxy"에서의 최대 길이인 "zzzz"를 구하지 못하게 된다.

왜냐하면 이 마나커 알고리즘은 어떤 중심점 하나에서 양 옆으로 확장하는 방식이기 때문이다.

 

이는 간단하게 해결할 수 있다.

문자열에 존재하지 않는 문자를 사이사이에 집어넣어 해결한다.

 

보통 "#"을 추가한다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val sb = StringBuilder()
    val input = readLine()
    for (c in input) {
        sb.append("#")
        sb.append(c)
    }
    sb.append("#")

    val list = MutableList(sb.length) { 0 }
    manachers(sb.toString(), list)

    var result = -1
    for (i in list.indices) {
        result = maxOf(result, list[i])
    }

    bw.write("$result")
    bw.flush()
    bw.close()
}

fun manachers(text: String, list: MutableList<Int>) {
    val length = text.length
    var r = 0
    var c = 0

    for (i in 0 until length) {
        if (r < i) list[i] = 0 else list[i] = minOf(list[2 * c - i], r - i)
        while (i - list[i] - 1 >= 0 && i + list[i] + 1 < length && text[i - list[i] - 1] == text[i + list[i] + 1]) list[i]++

        if (r < i + list[i]) {
            r = i + list[i]
            c = i
        }
    }
}

 

참고 자료:

https://m.blog.naver.com/jqkt15/222108415284

[알고리즘] Manacher’s Algorithm - 마나커(마나허) 알고리즘

 

https://00ad-8e71-00ff-055d.tistory.com/91

89. Manacher

 

https://school.programmers.co.kr/questions/73747?referer=collection-of-questions

프로그래머스