(13275) 가장 긴 팰린드롬 부분 문자열

https://www.acmicpc.net/problem/13275

단계별로 풀어보기

60단계(문자열 알고리즘 2) 1번째

 

 

 

56단계 수학3에서 갑자기 뛰었는데, 예전에는 이 단계가 수학3보다 위에 있어서 수학3을 다 풀기 전에 문자열 알고리즘 2를 전부 풀어서 그렇다.

 

문자열 S가 주어질 때 팰린드롬 부분 문자열을 찾는 매내처 알고리즘을 써야 하는 문제다. 만약 문자열의 어떤 인덱스 i부터 시작되는 팰린드롬 문자열이 있다고 하자. 팰린드롬의 범위 내라면 인덱스 i-j의 문자와 i+j는 같다. 만약 인덱스 i-j부터 시작되는 어떤 팰린드롬 문자열이 있다면, 이 팰린드롬 문자열은 인덱스 i+j을 중심으로도 찾을 수 있다. 이 특성을 이용한 것이 매내처이며, 인덱스 i을 중심으로 하는 팰린드롬의 최대 길이 배열을 구할 수 있다. 배열의 최대값을 출력하면 된다. 특성 상 매내처 알고리즘은 홀수 길이의 문자열에만 사용이 가능한데, 그래서 짝수 문자열은 문자마다, 그리고 문자열의 앞과 뒤에 더미 문자를 하나씩 넣어 강제로 홀수 길이 문자열로 바꿔줘야 한다. 따라서 매내처 알고리즘은 일반적으로 입력받는 문자열 길이를 강제로 두 배로 늘려야 하는데, 보통 PS에서는 상관없다.

팰린드롬 부분 문자열을 찾는 방법의 시간복잡도는 나이브하게 구현하면 O(N^3), DP로 구현하면 O(N^2), 매내처로 구현하면 O(N)이다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  string str, str2="#";

  cin >> str;
  
  vector<int> dp(str.length()*2+2);
  
  for(char c:str){
    str2+= c;
    str2+= '#';
  }
  
  int r= 0, p= 0, len= str.length()*2+1;
  
  for(int i=1;i<len;i++){
    if(i<=r)  dp[i]= min(r-i, dp[2*p-i]);

    while(i-dp[i]-1>=0 && i+dp[i]+1<len && str2[i-dp[i]-1]==str2[i+dp[i]+1])  dp[i]++;

    if(r<i+dp[i]){
      r= i+dp[i];
      p= i;
    }
  }

  cout << *max_element(dp.begin(), dp.end());

  return 0;
}