Manacher 알고리즘

앞서 dp파트에서 펠린드롬에 대한 문제를 풀어본 적이 있을 것이다. 펠린드롬이란 앞에서 읽었을때와 뒤부터 읽었을 때 결과가 똑같은 문자열을 의미한다. 또 다르게 생각해보면 정 중앙을 기점으로 퍼져나갈때 똑같은 문자가 등장하는 문자열을 의미한다.

기존 펠린드롬 구하기는 O(n^2) 의 시간이 소요됐었지만 이번에 소개할 알고리즘은 O(n) 이 걸리는 manacher 알고리즘이다. Manacher 알고리즘은 이전에 활용한 정보를 바탕으로 진행되는 알고리즘이다. 특정 위치를 중심으로 하는 펠린드롬을 구하는 것을 기본 전제로 하고 시작할 것이다.

만약 i번째를 중심으로 하는 펠린드롬을 구하려고한다고하자. 그런데 i보다 작은 index에 대해서 해당 index를 중심으로하는 펠린드롬들은 각각 왼쪽 끝과 오른쪽 끝이 존재할것이고 그 때 오른쪽 끝 index 값이 가장 클 때의 중심 index를 k라 하고 k를 중심으로 하는 펠린드롬의 오른쪽 끝 index를 r이라고 하자.

i가 r보다 클경우와 작은 경우로 나누어 펠린드롬을 찾아보자.

1. i > r

이전 정보를 하나도 활용할 수가 없는 경우로 i를 중심으로 하는 펠린드롬을 새롭게 찾아준다. i를 기점으로 한칸씩 양옆으로 이동하면서 비교를 해준다.
if S[i+p[i]+1] == S[i-p[i]-1] {p[i] += 1}

2. i ≤ r

자 이제 r 속에 i가 포함되는 경우를 생각해보자.

i는 k를 중심으로 하는 펠린드롬 속에 포함이 되어있다. k를 중심으로 i와 정반대에 있는 index를 i’ = 2k-i 이라고 하면 i와 i’은 대칭이기 때문에 i’을 중심으로 하는 펠린드롬은 i를 중심으로 하는 펠린드롬과 같다. 따라서 p[i] = min(p[i'], r-i) 가 성립하게 된다.

주의할 것은 p[i] = p[i’] 이 아니라는 것인데 r을 넘어서는 영역에 대해서는 펠린드롬 여부를 보장할 수가 없기 때문에 그 이후의 영역에 존재하는 문자들은 일일히 비교를 해가며 p[i] 값을 결정해주어야한다.

따라서 1에서 구했던 것과 마찬가지로 p[i] 값을 증가시키면서 i를 중심으로하는 펠린드롬의 길이를 찾아주자. 만약 i번째에 새롭게 구한 펠린드롬이 기존의 r보다 오른쪽 끝 index가 크다면 r과 k값을 새롭게 설정하면서 모든 index에 대해 펠린드롬을 구하면 된다.

• Manacher function

func manacher(str: [Character]) -> [Int] {
    let n = str.count
    var k = -1, r = -1
    var p = Array(repeating: 0, count: n)
    for i in 0..<n {
        if i <= r {
            p[i] = min(p[2*k-i], r-i)
        }
        while i-p[i]-1 >= 0 && i+p[i]+1 < n && str[i-p[i]-1] == str[i+p[i]+1] {
            p[i] += 1
        }
        if i+p[i] > r {
            r = i+p[i]
            k = i
        }
    }
    return p
}

Manacher 알고리즘은 i를 중심으로 하는 펠린드롬을 구하는 것이기 때문에 기본적으로 홀수의 길이를 갖는 펠린드롬만 구해진다. 만약 짝수를 구하고 싶다면 문자열 사이사이에 # 이나 @ 같은 안쓰는 기호로 모두 채워주면 간단히 해결할 수 있다. ABBA를 예로들면 #A#B#B#A# 가 되고 가운데에 위치하는 #에 대해 펠린드롬을 구해주면 짝수의 경우에도 찾아낼 수 있다.

모든 i에 대해서 초깃값 p[i]를 찾는 것은 O(1) 이 걸리게 되고 이 후 p[i] += 1 을 하는 횟수에 따라서 시간복잡도가 결정되게 된다. 그러나 p[i]가 증가하는 횟수는 r이 증가하는 횟수와 같고 최종적으로 r ≤ n 이기 때문에 O(n) 의 시간이 걸리게 된다.

추천 문제

백준 16163 #15164번_제보