백준 14444번 문제

[문제 설명]

알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

[처음 문제를 다뤘던 방법]

문제를 처음 봤을 때는 단순히 문자열의 길이만큼 for 문을 돌리면서 부분문자열과 하나씩 비교하면 해결되겠지 하는 생각이였지만... 문자열에 직접적인 처리를 하는 함수들은 생각보다 속도가 많이 느리다.

[문제 풀이 관련 알고리즘 - Manacher's Algorithm]

가장 긴 팰린드롬을 찾는 강력한 알고리즘으로 알려져 있다고 한다. 알고리즘을 다른 블로그나 위키를 보고 이해하는 데 조금 오래 걸렸다. 수학적 표현으로만 되어 있을 뿐 그에 대한 설명은 부실(?!)하다는 느낌이 많이 들었기 때문이다.

Manacher's Algorithm은 원리는 다음과 같다.

A[i]는 스트링에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬의 반지름을 나타낸다.
i < j 를 만족하는 i 중에서 가장 긴 반지름을 갖는 중심점을 p라 하고 문자열의 시작부분에서 중심점 p의 반지름을 더한 길이를 r이라고 하자.
그렇다면 r = p + A[p] ( p < j) 인 것을 알 수 있다.
String은 i 번째 Character 를 중심점으로 하는 A[i]를 DP를 활용하여 초기화 시킨다. 방법은 다음과 같다.
j <= r 이면(i < j 를 만족하는 i 중에서 가장 긴 반지름을 갖는 중심점 p에서의 팰린드롬의 반경 안에 존재한다는 의미) r - j 와 2* p - j ( j + j' = 2*p 임을 이용) 중 작은 값을 A[j]의 값으로 정한다.
j > r 이면(i < j 를 만족하는 i 중에서 가장 긴 반지름을 갖는 중심점 p에서의 팰린드롬의 반경 안에 존재하지 않는다는 의미) A[j]의 값은 0으로 한다.
그 후에 j 점을 중심으로 좌와 우를 비교하면 A[j]의 값을 증가시킨다.
기존의 r 값 보다 j + A[j]의 값이 크다면 r = j + A[j], p = j 로 갱신한다.
단, 이 방법은 문자열의 길이가 홀수일 때는 가능하다. 다만, 짝수일 때는 간단한 처리가 더 필요하다. 문자열의 맨 앞과 뒤, 문자 사이마다 '#'과 같은 문자를 삽입하는 것이다.