마나커 알고리즘 (Manacher's Algorithm)

`마나커 알고리즘` 이란

문자열 내의 회문을 빠른 속도로 판별해주는 알고리즘이다.

 

문자열의 개별 문자에서 양쪽 방향으로 전체 탐색을 하는 방법이 아닌,

기존에 탐색했던 값을 저장하여 활용하는 dp 성격을 띄는 알고리즘이다.

 

 

---

 

 

원리

먼저 알고리즘을 설명하기 앞서 회문의 성격에 대해 생각해보자.

 

 

회문의 성질은 다음과 같다.

• 중간 문자를 기준하여, 같은 거리만큼 떨어진 문자는 같다.
• 회문 내부에 회문이 존재할 수 있다.
• 하나의 글자도 회문이 된다.

 

회문 검사를 더 빠른 방식으로 하기 위해선

아무래도 2번 조건인 회문 내부의 회문을 검사하여 응용하는 방식이 유용해 보인다.

 

 

이때 주의해야 할 것이,

보통 회문 내부의 회문이라면, 아래 예시처럼 

특정 포인트를 기점으로 두 개의 같은 회문이 반복되는 케이스만을 생각하게 된다.

 

 

 

하지만 모든 회문이 위와 같은 케이스는 아니다.

위의 예시는 ☆A를 기준으로 반으로 자르면

또 ☆A를 기준으로한 회문 2개가 완성되지만,

다음과 같은 반례도 존재한다.

 

 

위와 같이, 내부 회문이 외부 회문의 정확히 반이 되지 않는 케이스가 있기에

☆A 기준 회문을 알아냈다고 해서 그의 두 배로 외부 회문을 보증할 수도,

혹은 ☆A를 찾아냈다고 하여 그의 반으로 내부 회문을 보증할 수도 없다.

 

그렇다면 내부 회문 정보를 이용하여 더 빠른 시간 내에 탐색할 방법은 없는 것일까?

 

마나커 알고리즘은 이러한 모든 케이스를 고려하며,

저장된 내부 회문 정보를 이용해 외부 회문 탐색의 시간을 줄여주는 솔루션을 제공한다.

 

[ 앞으로 이렇게 기존 회문을 벗어난 보라색의 경우를 외부 회문이라, ]

[ 큰 회문 내부의 작은 회문인 파란색의 경우를 내부 회문이라 편의상 칭하겠다. ]

 

 

---

 

 

적용

'마나커 알고리즘'은 회문 내의 회문 정보를 통해 탐색 인덱스를 단축하는 방법이다.

즉, 전체 탐색은 자신을 중점으로 양쪽을 다 검증해야 하지만,

'마나커 알고리즘'을 통해 보증된 몇 칸을 건너뛴 후 검증하여 탐색 시간을 줄일 수 있다.

 

먼저 계산의 편의성을 위해

각 자리가 정확히 중심부가 될 수 있도록

문자의 양 끝, 사이 모두에 특수 문자를 추가한다.

(이는 "ABBA" 처럼 짝수 개수의 문자 기준으로 중심이 형성되는 케이스를 망라하기 위함)

 

 

예시로 주어진 문자열은 "ABCBABCBA", 특수 문자로는 "#"을 추가한 경우를 통해 설명한다.

먼저 내부 회문 경우에 대해 살펴보자.

 

- mid : 0

- last : 0

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp

 

먼저 순차적으로 각 문자를 탐색하며, 해당 문자 기준 같은 방향으로 몇 칸까지 향했을 때 회문이 완성되는지 작성한다.

이를 이하 '반지름'이라 칭하겠다.

 

last는 현재까지 '가장 뒤쪽까지 향한 회문의 마지막 index (회문의 마지막)' 이고,

mid는 현재까지 '가장 뒤쪽까지 향한 회문의 중앙 index (회문의 중심부)' 이다.

 

 

 

예시로 index 1의 "A"의 경우 양쪽으로 한 칸씩 갔을 때 "#A#" 회문이 완성되니 1을 채운다.

이 회문은 index 2까지 이어지고, 회문의 가운데 글자인 "A"는 index 1이기에

last = 2, mid = 1이 된다.

 

- mid : 1

- last : 2

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp	0	1

 

또다른 예시로 index 2의 "#"의 경우, 한 칸씩 문자를 붙였을 때 "A#B"으로 회문이 완성되지 못하기 때문에 0을 채운다.

 

 

 

같은 방법으로 5번 index까지 순차적으로 진행한 후의 상황이다.

 

- mid : 5

- last : 10

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp	0	1	0	1	0	5

 

index 5의 "C"의 경우, index 0 ~ 10 까지의 "#A#B#C#B#A#" 의 문자가 회문을 이루기에

index 5까지 진행했을 때의 dp 값은 다음과 같고, mid 값은 "C"의 index인 5가 되며,

현재까지 '가장 마지막 index까지 진출한 회문'이 현재의 회문이기 때문에, last는 index 10이 된다.

 

 

 

index 6의 "#"은 당연히 0으로 채워질 것이고, 이제 index 7의 "B"까지 도달하였다고 가정해보자.

 

그림은 "#"을 포함하지 않았기 때문에 설명의 index와 다르다. index는 dp 표를 확인하길 바란다.

 

index 7의 "B"의 경우, 현재 가장 큰 회문 범위의 소속 문자열이면서,

중점을 기준하여 index 3의 "B"와 같은 거리만큼 떨어져 있다.

 

기존 index 3의 "B"같은 경우, dp[3] == 1 으로 "#"을 제외한 회문이 만들어지지 않았기 때문에, ( A#B#C )

현재 index 7의 "B" 경우도, 같은 회문의 반대편이기에 "#"을 제외한 회문이 만들어지지 않음을 알 수 있다. ( C#B#A )

 

이렇게 현재 탐색 중인 문자열이 회문에 속해 있을 때,

중앙 기준 반대편의 쌍둥이 문자열에 대한 dp 정보로 탐색 시간을 줄이는 것이 '마나커 알고리즘'의 원리이다.

 

 

 

index 8까지 진행된 후의 상황이다.

 

- mid : 5

- last : 10

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp	0	1	0	1	0	5	0	1	0

 

현재까지 last index 10을 넘어가는 회문을 만들지 못했기에 mid 와 last 는 index 5의 "C" 기준 회문으로 고정되어 있다.

 

 

 

이제 index 9의 "A"를 살펴보자.

 

 

기존 파란색 회문 내에서 아직 진행 중이지만, index 9의 "A"는 기존 회문을 뛰어넘어 더 큰 회문을 만들기에

mid 와 last 의 값이 현재 회문의 기준으로 조정된다.

 

- mid : 9

- last : 18

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp	0	1	0	1	0	5	0	1	0	9

 

 

 

 

이제 index 13을 살펴보자.

 

 

index 13의 "C"의 경우, 현재 가장 큰 보라색 회문에서 ☆A를 중점으로 같은 거리만큼 떨어진 index 5의 "C"와 성질이 같다.

이는 ' 나와 성질이 같은 index 5의 "C"가 이미 5(dp[5]) 만큼의 회문을 검증했으니, 내 주변에도 5만큼의 회문이 있겠군 '

과 같은 의미이며, 따라서 추가적인 탐색 없이 dp[5]의 값을 그대로 채워 넣을 수 있다.

 

다만 index 13의 "C"가 형성하는 회문의 last가 기존 보라색 회문을 초과하지 못하므로, mid와 last는 유지한다.

 

- mid : 9

- last : 18

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp	0	1	0	1	0	5	0	1	0	9	0	1	0	5

 

 

 

이후 최종 dp 테이블은 다음과 같이 작성된다.

 

- mid : 9

- last : 18

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	A	#	B	#	C	#	B	#	A	#	B	#	C	#	B	#	A	#
dp	0	1	0	1	0	5	0	1	0	9	0	1	0	5	0	1	0	1	0

 

 

 

여태까지는 내부 회문만의 예시만 살펴 보았는데, 만약 외부 회문이 개입된다면 어떻게 될까?

일전의 예시로 든 "CABABABAC" 로 살펴보자.

 

 

 

index 8까지 진행된 후의 상황이다.

 

- mid : 7

- last : 12

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
str	#	C	#	A	#	B	#	A	#	B	#	A	#	B	#	A	#	C	#
dp	0	1	0	1	0	3	0	5	0

 

 

현재 파란색 범위까지 진행된 상황이며, 다음 index 9에서 보라색 범위로 갱신되는 계산이 필요해졌다.

 

index 9의 "B"는 ☆A를 중점으로 한 회문에서 index 5의 "B"와 성질이 같으므로,

dp[5]에 방문하여 같은 성질인 index 5의 "B"가 자기 자신을 중점으로 몇 반지름 길이의 회문을 만드는지 알아낼 수 있다.

 

 

dp[5]를 통해 index 9의 "B" 또한 이미 회문의 반지름이 3만큼 만들어진 것을 알 수 있다.

 

따라서 현재 index 9를 중심으로 index 6 (9-3) ~ index 12 (9+3) 까지는 회문임을 알 수 있기에 탐색하지 않아도 되며,

이후 index 5 (6-1) 와 index 13 (12+1) 부터 양쪽으로 순차적으로 비교하며 추가적인 외부 회문이 있는지 검증하는 과정을 거쳐야 한다.

 

 

 

이때 주의해야 할 점은 외부 회문 탐색을 위해 반지름을 계산하는 과정에서,

기존 회문의 올바른 범위 내에서 반지름을 계산해야 한다는 점이다.

 

 

다음과 같은 예시에서 오른쪽 X의 외부 회문 탐색을 위해 dp[왼쪽 X index]를 접근할 때,

 

왼쪽 X의 경우 양쪽 문자가 같아 dp의 값은 3이 나오지만,

오른쪽 X의 경우 양쪽 문자가 달라 dp의 값이 1이므로,

 

dp[왼쪽 X index] 값을 바로 사용하게 되면 논리적인 오류를 발생 시킬 여지가 있다.

 

따라서 dp[쌍둥이 index] 를 접근하되, 해당 값이 회문을 보증하는 index를 넘을 경우엔 옳지 않다.

이는 'dp[쌍둥이 index]' 가 실제로는 '회문을 보증하는 last index - 현재 index' 만큼만 유효하다는 의미로,

Math.min(dp[쌍둥이 index] , last - i) 로 유효 반지름을 계산할 수 있다.

 

추가로 쌍둥이 index를 계산하는 방법은 중점 기준, 현재 탐색 중인 위치와 쌍둥이 index의 거리가 같기 때문에,

[ 쌍둥이 index + ? = mid = 현재 탐색 중인 위치(i) - ? ] 의 방정식으로

mid - (i - mid)  =  2mid - i,

즉, dp[2*mid - i] 가 쌍둥이 index의 실제 값이 된다.

 

 

 

dp 배열이 모두 채워졌다면, dp 배열을 순회하며 가장 큰 값의 원소가 정답이 된다.

 

우리는 "#"을 추가한 문자열을 통해 값을 도출했기 때문에 실제 정답은 dp[i]에서 추가적인 연산을 해줘야 할 것 같지만,

dp[i] 값이 '자신을 제외한 반지름 길이' 이고 이를 x라 했을 때, "#" 및 자신을 포함한 문자열의 길이는 2x+1,

전체 문자열에서 "#"은 실제 문자의 수보다 항상 1개가 더 많으므로 ( (2x+1) - 1 ) / 2 가 실제 문자의 개수가 되어

결국 dp[i] 의 값이 실제 회문을 이루는 "#" 을 제외한 문자의 길이와 동일하다는 것을 알 수 있다.

따라서 별도의 연산 없이 max(dp[]) 를 구하여 return 해주면 된다.