Manacher's Algorithm

팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다.

 

이 팰린드롬을 찾기 위한 알고리즘 중 하나가 Manacher's Algorithm이다.(시간 복잡도 O(n))

 

문자열 S=bananac로 팰린드롬을 찾아보는 연습을 해보자.

 

A[i]는 i번째 문자를 중심으로 하는 가장 긴 반지름을 뜻한다 -> S[4]는 문자 a를 뜻하고 A[4]는 문자 a를 기준으로 S[2]와 S[6]에 있는 a까지의 거리(반지름)을 뜻한다.

 

S[i]	b	a	n	a	n	a	c
A[i]	0	0	1	2	1	0	0

 

이 알고리즘의 동작 원리를 살펴보자.

1. i는 1부터 N까지 진행된다.

2. j<i인 모든 j에 대해 r=max(j+A[j])라 하고 그러한 j를 p라고 한다. (r=p+A[p])

3-1. i > r이면 A[i]의 초기값은 0이다.

  -2. i<=r이면 i는 p가 중심인 팰린드롬 안에 속한다. 그때 i의 대칭점을 i'라 하면 i'=2p-i가 된다. 그리고 A[i]의 초기값은 min(r-i,A[i'])다.

4. A[i]의 초기값이 결정되고, S[i-A[i]]와 S[i+A[i]]가 같을 때까지 A[i]를 증가시킨다.

 

이대로 해석을 해보자.

1. A[i]는 반지름을 의미, i는 자릿수를 의미한다 -> i는 1부터 N까지 진행 -> 7개 자릿수이므로 1부터 7번까지 진행

2. r=max(j+A[j])가 의미하는 것은 r이 존재할 경우 팰린드롬 중심에서 반지름을 더한 값의 자릿수를 의미하고 이때의 j를 p라고 한다면 이 p는 팰린드롬의 중심을 의미한다.

3. i>r이라는 것은 팰린드롬이 아님을 의미하므로 A[j]는 0이다. 

    i<=r일때 p는 위에서 말했듯 팰린드롬의 중심을 의미하고 i는 그 팰린드롬 중심에서 p+A[p]까지의 자릿수 중 하나이며 i'라는 것은 i의 대

    칭점이므로 i'=2p-i 즉, 중심에서 p-A[p]만큼 떨어진 자릿수를 의미한다. A[i]의 초기값이 min(r-i, A[i'])이라는 것은 아직 의미를 모르겠

    다. (예시 문자열 S로 살펴보면 S[4], 즉 문자 a를 계산할때 i'와 i의 양옆이 팰린드롬인 것을 확인했기 때문에 그대로 가져올 수 있는 것으

    로 보인다. 가져오고 나서는 양옆이 아닌 양옆+1,-1의 문자를 비교한다.)

4. A[i]의 초기값이 결정되고 i를 중심으로 양쪽 문자열이 같을때까지 반지름을 증가시킨다.

 

이를 토대로 표를 만들어 작성해보자. ( ()안의 숫자는 1부터 N이 아닌 0부터 N-1까지의 인덱스를 나타낸다)

S[i]	b	a	n	a	n	a	c
i	1(0)	2(1)	3(2)	4(3)	5(4)	6(5)	7(6)
A[i]	0	0	0->1	0->1->2	1	0	0
r	0	0->1	1->3	3->5	5	5	5
p	0	0->1	1->2	2->3	3	3	3

 

이젠 코드를 작성해보자.

 

참조 사이트 https://www.crocus.co.kr/1075

Manacher 알고리즘(Manacher's Algorithm)