[백준 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에 해당하는 팰린드롬 문자열의 중심 인덱스

 

	// BOJ 13275
	// Manacher Algorithm
	#include <bits/stdc++.h>
	using namespace std;
	struct node {
	int r; // radius
	int p; // preserve
	int c; // center
	};
	vector<node> manacher(string s) {
	int n = size(s);
	s.resize(2*n+1);
	s[2*n] = '#';
	for (int i=n-1; i>=0; i--) {
	s[2*i+1] = s[i];
	s[2*i] = '#';
	}
	vector<node> ret(2*n+1, {0, 0, 0});
	for (int i=0; i<=2*n; i++) ret[i].c = i;
	int dp_p = -1;
	int dp_c = 0;
	for (auto &[r, p, c] : ret) {
	if (c <= dp_p) {
	int cor_r = ret[2*dp_c-c].r;
	r = min(dp_p-c, cor_r);
	}
	else r = 0;
	while ( (c-r >= 0 && c+r <= 2*n) && (s[c-r] == s[c+r]) ) r++;
	r--;
	if (c+r > dp_p) tie(dp_p, dp_c) = make_pair(c+r, c);
	tie(p, c) = make_pair(dp_p, dp_c);
	}
	return ret;
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s; cin >> s;
	auto arr = manacher(s);
	int ans = 0;
	for (auto &[r, p, c] : arr) {
	if (c%2 == 0) ans = max(ans, r);
	if (c%2 == 1) ans = max(ans, r);
	}
	cout << ans << '\n';
	return 0;
	}

view raw 13275.cpp hosted with ❤ by GitHub