[C++ 알고리즘] 백준 14444 가장 긴 팰린드롬 부분 문자열

[백준] 14444 가장 긴 팰린드롬 부분 문자열 cpp 풀이

문자열, 매내처 알고리즘

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

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

문제 요약

- 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 출력하면 된다. 

- 문제는 짧지만, 문자열 S를 글자 하나씩, 글자 두개씩, 글자 세개씩 잘라서 각각이 팰린드롬인지 확인해야 한다고 생각했다. 

풀이 정리

1. 역시나, 그냥 다 해보는 것이다. 문자열의 길이가 n이라고 한다면, 문자열의 길이가 1인 경우 나올 수 있는 조합(n개), 2인 경우 나올 수 있는 문자열(n-1개), ... , n인 경우(1개) 등등의 모든 문자열에서 각각이 팰린드롬인지 확인하는 방법이다. 

2. 매내처 알고리즘을 활용하는 것. 매내처 알고리즘은 문자열 배열에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬 길이를 반지름 r로 저장하여 사용하는 것이다. 

 

C++ 코드

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

string s;
int A[200001];
char arr[200001];

void manachers(int N){
    int r=0, p=0;
    
    for(int i=0; i<N; i++){
        if(i<=r) A[i] = min(A[2*p-i], r-i);
        else A[i] = 0;

        while(i-A[i]-1 >=0 && i+A[i]+1 < N && arr[i-A[i]-1] == arr[i+A[i]+1])
            A[i]++;
        
        if(r<i+A[i]){
            r=i+A[i];
            p=i;
        }
    }
}

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin>> s;
    int N=s.size();
    
    for(int i=0; i<s.size(); i++){
        arr[i*2]='#';
        arr[i*2+1] = s[i];
    }
    N=N*2+1;
    arr[N-1]='#';
    
    manachers(N);
    
    int mmax=-1;
    for(int i=0; i<N; i++){
        if(A[i]>mmax) mmax=A[i];
    }
    cout << mmax;
    
    return 0;
}