Manacher's Algorithm, 펠린드롬

길이가 N인 문자열이 있을 때, 펠린드롬을 가장 빠르게 판단할 수 있는 방법은 마나체스 알고리즘이다.

 

시간 복잡도는 O(N)이다.

 

---

 

 

Manacher's algorithm은 문자열 내에서 팔린드롬(palindrome,회문)을 찾는것과 관련된 알고리즘이며, 시간 복잡도는 O(n) 이다.(n은 문자열의 길이)

이 알고리즘은 문자열 S를 입력으로 받아 다음을 반환한다:

• 문자열 S와 길이가 같은 정수 배열 A, 각 A의 원소 A[i]는 i번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉, S[(i−A[i])⋯(i+A[i])]는 팔린드롬이며, S[(i−A[i]−1)⋯(i+A[i]+1)]은 팔린드롬이 아니다)

예를 들면, S='banana'라는 입력에 대해 A의 결과는:

 

알고리즘은 다음과 같다:

1. i는 0부터 n−1(n=|S|)까지 진행된다
2. j<i인 모든 j에 대해 R=max(j+A[j])이라하고, 또한 그러한 j를 p라 하자. 즉, R=p+A[p]
3. i≤R인지 여부에 따라 A[i]의 초기값이 정해진다
   • i>R이라면, A[i]의 초기값은 0이다.
   • i≤R이라면, i는 p를 중심으로 한 팔린드롬에 속한다는 이야기이다. 이때 p를 중심으로 i의 대칭점 i′을 구한다. (즉, i′=2∗p−i) A[i]의 초기값은 min(R−i,A[i′])으로 둔다.
4. A[i]의 초기값에서부터, S[i−A[i]]과 S[i+A[i]]가 같을 때까지 A[i]를 증가시키고, 그 다음 i로 넘어간다.

의사코드로 구현하면 다음과 같다:

 

 

 

---

 

 

위의 글은, https://algospot.com/wiki/read/Manacher's_algorithm에서 긁어왔다.

 

 

마나체스 알고리즘에 대해서 정확하게 이해하고 있다면, 위의 글이 잘 읽힌다. 하지만, 나처럼 처음 읽어보는 사람들은 알고리즘에 대해서 이해하기가 쉽지 않다.

 

 

내가 겪은 시행착오를 바탕으로 아주 쉽게 자세히 설명을 하고자 한다.

 

 

---

 

 

 

위의 알고리즘을 바탕으로 한 줄씩 설명하겠다.

 

 

 

1. i는 0부터 n - 1까지 시작된다.

- i라는 것은, 문자열을 가르키는 인덱스로 사용된다. 시간복잡도가 O(N)이라고 했으니, 문자열의 모든 문자에 대해서 검사를 한다.

 

 

 

2. j < i인 모든 j에 대해 R = max(j + A[j])이라 하고, 또한 그러한 j를 p라 하자. 즉, R = p + A[p]

- banana에서 만약에 i = 3인 a를 검사한다고 해보자. 그렇다면, j는 0, 1, 2가 될 수 있다. R은 특정 문자에서 팰린드롬의 최대 길이라고 보면 된다. R을 찾는 과정은, 지금까지 검사한 문자들중에서 가장 긴 팰린드롬의 최대 반경을 찾는 것이다. 

 

 

 

3. i≤R인지 여부에 따라 A[i]의 초기값이 정해진다

• i>R이라면, A[i]의 초기값은 0이다.
• i≤R이라면, i는 p를 중심으로 한 팔린드롬에 속한다는 이야기이다. 이때 p를 중심으로 i의 대칭점 i′을 구한다. (즉, i′=2∗p−i) A[i]의 초기값은 min(R−i,A[i′])으로 둔다.

 

 

- 이 부분에서, 이해하는데 어려움을 겪었다. 이 부분을 좀 자세히 설명하고자 한다. R이라는 것은 위에서 가장 긴 팰린드롬의 최대 반경이라고 이해했다. 최대 반경에 속하지 않으면(i > R), A[i]의 초기값은 0이 되어야 하는 것이 맞다. 여기서 0은 그 문자 자체가 팰린드롬이라는 것을 나타낸다.

 

 

 

- 자 여기서, i≤R인 부분을 이해하는 것이 가장 중요하다. 우선 대칭점 i'라는 것은 (i' + i) / 2 = p의 식을 통해서,

i' = 2*p  - i라는 것을 구할 수 있다.

 

 

 

 그렇다면, 왜  A[i]의 초기값이 min(R-i, A[i'])일까? 우선, p는 양의 방향으로 최대 반경 R을 가지고 있는 펠린드롬이다. R'을 p의 최대 반경이지만 음의 방향이라고 생각하자. R' = p - A[p]라고 생각할 수 있다. 만약에 A[i']이 R'을 넘어서 팰린드롬을 유지한다고 하면, 이 A[i']값은 i'에만 한정적으로 적용되는 것이다. 왜냐하면, i'이 가지고 있는 가장 긴 펠린드롬 문자열이, i도 가진다고 볼 수 없다! 따라서, 최적의 선택으로 R-i로 끊어져야 하는 것이 맞다.

 

 

 

A[i']이 만약에 p의 펠린드롬 내부에서, 즉 R'내에서 가장 긴 펠린드롬을 가진다면 그 값은 A[i]에도 똑같이 적용된다!

 

 

 

이 두가지 관계를, min(R-i, A[i'])을 통해서 나타내고 있는 것이다.

 

 

 

4. A[i]의 초기값에서부터, S[i−A[i]]과 S[i+A[i]]가 같을 때까지 A[i]를 증가시키고, 그 다음 i로 넘어간다.

- 위의 방식으로 A[i]의 초기값을 만들고, 가장 긴 펠린드롬을 파악하는 과정이다.

 

 

 

---

 

 

위, 4가지 단계를 정확하게 파악한다면, 의사코드로 표현할 수 있다. 

누군가에게 이 설명이 도움이 되길 바란다!