[알고리즘] 매내처 알고리즘(Manacher) 개념

출처: unsplash.com

 

 

매내처 알고리즘이란?

문자열 S가 주어질 때, 팰린드롬 부분 문자열을 찾는 알고리즘을 뜻한다.

 

팰린드롬 부분 문자열은 S의 부분 문자열 중 팰린드롬인 경우를 의미한다(banana에서 anana가 부분 문자열 팰린드롬이다).

모든 i에 대해 i번 문자가 중심인 최대 길이의 팰린드롬 부분문자열을 검색하는 알고리즘.

팰린드롬의 길이는 주로 팰린드롬의 반지름의 형태로 저장된다(반지름이란, 팰린드롬의 중심으로부터 가장 먼 문자가 얼마나 떨어져 있는지를 확인하기 위한 것이다(aba에서 반지름은 1이 된다).
팰린드롬의 길이가 i라면 반지름은 (i -1) / 2가 된다.

 

매내처 알고리즘을 알아보기 전에 팰린드롬이 정확히 무엇인지 짚고 넘어가자.

 

팰린드롬(회문, palindrome)

뒤집어도 같은 문자열을 뜻한다.

거꾸로 읽어도 같은 문자열이 팰린드롬의 예이다.

 

한 글자로 이루어진 모든 문자열은 회문이다.

• a, b, c 등등

다음과 같은 문자열은 모두 팰린드롬이다.

• bob, abcba, level 등등

다음과 같은 문자열은 모두 회문이 아니다.

• banana, array, manacher 등등

 

팰린드롬의 성질

팰린드롬은 거꾸로 읽어도 원래 문자열과 동일하다(정의와 같음)

각 팰린드롬은 중심이 되는 축을 가진다.

팰린드롬의 길이가 n일 때 n이 홀수인 경우는 (n+1) / 2번째 문자가 중심이 되고,

n이 홀수인 경우, n / 2번째, n / 2 +1번째 문자 사이가 축이 된다.

팰린드롬의 앞뒤에 같은 문자를 붙이면 계속 회문이 된다.

앞뒤에 같은 문자를 붙일 경우, 뒤집었을 때도 앞뒤에 같은 문자를 붙이게 되기 때문(aba -> aabaa: 둘 다 팰린드롬이다).

 

 

Manacher 알고리즘 - 예시

S = banana, A[i]: i번 문자를 중심으로 했을 때 최대 반지름일 때

 

A[0] = 0: banana

A[1] = 0: banana

A[2] = 1: banana

A[3] = 2: banana

A[4] = 1: banana

A[5] = 0: banana

위와 같은 팰린드롬을 만들 수 있다(글자가 초록색인 부분이 팰린드롬이다).

A[i]를 돌면서 A[i]를 팰린드롬의 중심으로 삼고 앞뒤로 늘려가면서 같은 값이 있는지 체크하는 것이다.

 

알고리즘의 계산

A[i]를 0으로 초기화하고,
S[i - A[i] - 1]이랑 S[i + A[i] + 1]이 같다면 A[i]를 1씩 늘려 준다.
위의 예를 예시로 들면 i가 1일 때, S[i - A[i] - 1]는 S[0]가 되고, S[i + A[i] + 1]는 S[2]가 된다.
두 문자가 달리지거나 문자열의 끝에 도달할 때까지 반복한다.

 

 

최적화 계산

문자열의 대칭성을 이용해 A[i]를 빠르게 계산해 줄 수 있다.

어떤 대칭축이 j에 있을 때, i와 2j-i가 있을때, 다음과 같은 공식이 성립된다.

A[i] == A[2j-i]

 

i + A[2j - i]가 j + A[j] 이상인 경우는 j +A[j] + j가 보장된다.

사진의 파란 선이 초록 선을 벗어나는 경우는 예외 사항이 될 수 있으므로 다른 방언을 제안하겠다.

 

j + A[j]가 가장 큰 j를 고른다.

i + A[2j - i]가 j + A[j]보다 작은 경우는 A[i] = Z[2j - i]이다.

그렇지 않으면, Z[i]를 j + A[j] - i부터 시작해 1씩 늘려가면서 계산한다.

 

예제 - 최대 길이의 팰린드롬 부분 문자열

Manacher 알고리즘을 1회 수행한다.

각 문자를 중심으로 한 최대의 길이 부분 문자열 중 가장 긴 것을 찾는다.

모든 회문은 중심축을 가지므로 문제 해결이 될까? 짝수 길이의 회문은 중심이 되는 문자가 2개이므로 탐색이 불가하다.

 

팰린드롬이 짝수인 경우에는 S의 문자 사이사이에 특수기호를 끼운다. 맨 앞 맨뒤 포함.

예) ababa -> ?a?b?a?b?a

끼울 문자가 문자열에 없는 문자일 필요는 없다.

 

 

 

정리

매내처 알고리즘은 오직 팰린드롬을 쓸 때만 사용할 수 있는 알고리즘이다.

범용성은 떨어질 수 있어도 부분 팰린드롬을 빠르게 구할 수 있는 알고리즘이기에 빠르게 이해해서 코드에서 써먹을 수 있도록 해야겠다..(아직은 이해가 어렵다)