[백준 13275번] 가장 긴 팰린드롬 부분 문자열

13275번: 가장 긴 팰린드롬 부분 문자열

---

 

목차

• 관련 개념
• 문제 접근
• 풀이

 

 

관련 개념

• 팰린드롬 부분 문자열 DP 풀이 (링크)
• 팰린드롬 부분 문자열 Manacher 알고리즘 (링크)

 

팰린드롬 문자열의 성질

• 길이가 홀수인 경우에 가운데 문자가 중심이 된다.
• 길이가 짝수인 경우에 가운데 두 문자 사이가 중심 축이 된다.
• 팰린드롬 문자열은 앞 뒤에 같은 문자를 붙이면 계속 팰린드롬 문열이 된다.

 

 

 

문제 접근

문자열 $\small{S}$의 부분 문자열 중에서 가장 긴 팰린드롬 문자열의 길이를 출력하는 문제이다. ($\small{1 \leq |S| \leq 10^5}$)

 

접근1 - O(N³)

가장 네이티브 한 방법으로 모든 부분 문자열을 탐색하면서 팰린드롬인지 확인하는 방법이 있다.

만약 해당 부분 문자열이 팰린드롬이면 최대값을 갱신해 나가면서 진행하면 된다.

부분 문자열의 경우의 수가 $\small{_{|S|}\mathrm{C}_2}$이며, 각 부분 문자열이 팰린드롬인지 확인하는 데 걸리는 시간은 상한 $\small{|S|}$이다.

 

접근2 - O(N²)

위의 접근1은 팰린드롬의 특성을 전혀 고려하지 못한 풀이이다.

어떤 문자열 $\small{s}$의 가운데 인덱스를 $\small{i}$라고 해보자. 그리고 $\small{s[i-\alpha:i+\alpha]}$와 $\small{s[i-\beta:i+\beta]}$의 관계를 살펴보자. ($\small{\alpha < \beta}$)

$\small{s[i-\alpha:i+\alpha]}$가 팰린드롬 문자열이면 $\small{s[i-\beta:i+\beta]}$는 팰린드롬 문자열일 수도 있고 아닐 수도 있다.

하지만, $\small{s[i-\alpha:i+\alpha]}$가 팰린드롬 문자열이 아니라면 $\small{s[i-\beta:i+\beta]}$는 팰린드롬 문자열이 될 수 없다.

 

이러한 특성을 이용하여, 입력으로 주어지는 $\small{S}$의 모든 인덱스를 가운데로 취하여 확인하면 된다.

즉, $\small{|S|}$만큼의 경우의 수를 가운데로 취하여 확인하며 각 원소에서 상한 $\small{|S|}$ 만큼 살펴보면 된다.

(살펴볼 때 팰랜드롬이 아니라면 건너 뛰므로 실제 시간 복잡도는 이보다 더 작음을 짐작할 수 있다.)

 

 

문제에서 주어지는 $\small{|S|}$의 최대값이 $\small{10^5}$이므로 좀 더 효율적인 방법을 생각해야 한다.

 

 

 

풀이 - O(N)

이 풀이는 Mahacher 알고리즘(링크)을 이용한 풀이이며, 위에서 설명한 접근2를 최적화한 방법이라 할 수 있다.

Manacher 알고리즘은 팰린드롬 부분 문자열을 모두 찾는 알고리즘이다.

 

핵심 아이디어

위에서 설명한 접근2는 $\small{O(N^2)}$ 풀이로 각 원소들에 대해 꽤 많이 중복 접근한다.

이전에 접근한 정보를 통해서 조금 더 효율적으로 팰린드롬 부분 문자열의 후보를 살펴보는 것이 핵심 아이디어이다.

Manacher 알고리즘은 이전에 발견한 팰린드롬 문자열의 대칭성을 이용하여 이후에 팰린드롬 문자열을 효율적으로 탐색한다.

 

Manahcer 알고리즘은 각 인덱스에 대해 아래와 같은 정보를 저장하며 진행된다.

• r: 인덱스 i를 기준으로 가장 긴 팰린드롬 문자열의 반지름
• p: 인덱스 i까지 살펴 봤을 때 찾은 팰린드롬이 미치는 최대 범위 인덱스
• c: p에 해당하는 팰린드롬 문자열의 중심 인덱스