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

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

github : https://github.com/junho0956/Algorithm/blob/master/13275/13275/%EC%86%8C%EC%8A%A4.cpp

 

manacher's Algorithm 을 통하여 해결했습니다.

 

manacher's 알고리즘을 구현시 dp에는 인덱스 i 기준 팰린드롬을 만들 수 있는 범위가 설정됩니다.

이를 이용하면 가장 긴 팰린드롬 부분 문자열을 만들 수 있습니다.

단 짝수의 경우가 있으니 문자열 사이에 임의의 문자열을 삽입하여 홀수로 만들고 시작합니다.

 

dp를 갱신해가면서 그 범위를 max를 통해 저장해두고 마지막에 그 값에 대한 정답을 출력하면,

스트링의 첫 부분과 마지막 부분에 대한 반례가 생길 것 같았습니다.

그 이유는 짝수를 고려한 부분문자열을 추가했기 때문입니다.

 

그래서 현재 dp[i] 에 대해서 스트링 str의 값이 # 인지 아닌지로 먼저 구별하였고,

str[i+dp[i]] 가 # 인지 아닌지 재구별하였습니다.

만약 #이면 정확한 길이가 아니기 때문입니다.

그 후에는 dp[i]의 값이 짝수인지, 홀수인지에 따른 실제 길이를 계산해주었습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int dp[200010];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string a, str;
    int len;
 
    cin >> a;
    for (int i = 0; i < a.size(); i++) {
        str += a[i];
        str += '#';
    }
    str.pop_back();
 
    int r = 0, p = 0;
    len = str.size();
 
    for (int i = 0; i < len; i++) {
        if (i <= r) dp[i] = min(r - i, dp[p*2-i]);
        else dp[i] = 0;
        while (i + dp[i] + 1 < len && i - dp[i] - 1 >= 0 && str[i + dp[i] + 1] == str[i - dp[i] - 1]) dp[i]++;
        if (i + dp[i] > r) {
            r = i + dp[i];
            p = i;
        }
    }
 
    int ans = 0;
    for (int i = 0; i < len; i++) {
        if (dp[i]) {
            // even
            if (str[i] == '#') {
                int temp = dp[i];
                if (str[i + dp[i]] == '#') temp--;
                int cnt = (temp / 2 + 1) * 2;
                ans = max(ans, cnt);
            }
            // odd
            else {
                int temp = dp[i];
                if (str[i + dp[i]] == '#') temp--;
                int cnt = temp+1;
                ans = max(ans, cnt);
            }
        }
    }
    if (ans == 0) ans = 1;
    cout << ans;
 
    return 0;
}