Rolling Dev

Manacher's Algorithm in Go

Posted on Jan 24, 2024
tl;dr: -

인터넷에 설명이 많은데, 간단한 내용에 비해 설명이 너무 어려워서 직접 글을 쎠보았다.

In a Nutshell

  1. 전체과정
문제:
    s = "abaaba" 일 때
과정:
    s' = "#a#b#a#a#b#a#"로 변환하고
    i = 0..n-1 에 대해 p[i]를 계산한다.
정답:
    p = {0,1,0,3,0,1,6,1,0,3,0,1,0}
  1. 성능

$O(n)$ (n: len(s))

P (Palindromic Substring)

P를 구하는 것이 핵심이다.

p[i]: i를 중심으로 하는 Palindromic Substring의 반경

문자열 s에서 인덱스 i를 0에서부터 증가시키며 p[i] 값을 찾는다.

예시1: s = "abaaba

먼저 p 값에 대해 이해해보자.

      0  1  2  3  4  5  6  7  8  9 10 11 12
s'  | #  a  #  b  #  a  #  a  #  b  #  a  #
p   | 0  1  0  3  0  1  6  1  0  3  0  1  0
Palindromic Substring P value (radius)
lps[0] #------------ 0
lps[1] #a#---------- 1
lps[2] --#---------- 0
lps[3] #a#b#a#------ 3
lps[4] ----#-------- 0
lps[5] ----#a#------ 1
lps[6] #a#b#a#a#b#a# 6
lps[7] ------#a#---- 1
lps[8] --------#---- 0
lps[9] ------#a#b#a# 3
lps[10] ----------#-- 0
lps[11] ----------#a# 1
lps[12] ------------# 0

여기까지는 그냥 평범한 Dynamic Programming이고, 여기서 특별한 아이디어를 더한 것이 Manacher’s algorithm이다.

위의 예시에서 만약 p[0..6]를 구해놓고 p[7]값을 구할 때, 우리는 이미 답을 알고있다. 왜냐하면 p[6]의 Palindromic substring이 이미 문자열 전체를 아우르는 값이기 때문에(#a#b#a#a#b#a#), p[5], p[7]에서 반드시 좌우 대칭이 보장되기 때문이다.

      0  1  2  3  4  5  6  7  8  9 10 11 12
s'  | #  a  #  b  #  a  #  a  #  b  #  a  #
p   | 0  1  0  3  0  1  6  ✓
                     |  ◆  ▲
                     └-----┘

p[8..12]에서도 마찬가지다. 전부 p[6]에서의 Palindromic substring에 포함되기 때문이다.

      0  1  2  3  4  5  6  7  8  9 10 11 12
s'  | #  a  #  b  #  a  #  a  #  b  #  a  #
p   | 0  1  0  3  0  1  6  ✓  ✓  ✓  ✓  ✓  ✓
      |  |  |  |  |  |  ◆  ▲  ▲  ▲  ▲  ▲  ▲
      |  |  |  |  |  └-----┘  |  |  |  |  |
      |  |  |  |  └-----------┘  |  |  |  |
      |  |  |  └-----------------┘  |  |  |
      |  |  └-----------------------┘  |  |
      |  └-----------------------------┘  |
      └-----------------------------------┘

예시2: s = "abaabab

그럼 예외상황에서 생각해보자.

      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
s'  | #  a  #  b  #  a  #  a  #  b  #  a  #  b  #
p   | 0  1  0  3  0  1  6  1  0  3  0  ?     ?
      <-                ◆                ->   
                              <-       ◆       ->
                                          <- ◆ ->

p[11]에서는 p[1]을 그냥 복사하면 1이 되지만, p[9]==p[13]=='b'가 되기 때문에 올바른 값은 3이다. 그렇다면 최선의 전략은 복사한 값을 이미 알고있는 정보로 생각해서 생략하고, 그 너머에서 좌우대칭을 검사하는 것이다.

p[13]에서는 p[6]의 Palindromic substring의 범위를 벗어나기 때문에, 더이상 대칭하는 값이 없다. 따라서 p[13] 이후부터는 p[6]의 정보를 버리고 새로운 대칭 범위를 찾아서 업데이트해야한다. 그리고 p[12]는 어차피 값이 0이기 때문에 이 경우에도 버릴 것이다.

Manacher’s Algorithm

전체 알고리즘은 짧다. 조금 지저분한데 그래도 동작한다.

func manacher(s string) []int {
    s = _joinString(s)
    n := len(s)
    p := make([]int, n)
    l, r := 0, 0                        // current rightmost palindrome

    for i := 1; i < n-1; i++ {
        x := 0
        if i < r {
            x = p[l+(r-i)]              // copy mirror value
        }

        for ; x < min(i, n-i-1); x++ {
            if s[i-x-1] != s[i+x+1] {   // check palindrome centered at i
                break
            }
        }

        p[i] = x

        if r < i + x {
            l = i-x; r= i+x             // update mirror variable
        }
    }

    return p
}

func _joinString(s string) string {
    b := bytes.Buffer{}
    b.WriteByte(0)
    for i := 0; i < len(s); i++ {
        b.WriteByte(s[i])
        b.WriteByte(0)
    }
    return b.String()
}

참고