백준 14444 가장 긴 팰린드롬 부분 문자열

 

 

주어진 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제입니다.

문자열의 길이가 10만이므로 단순히 찾아보는 방법으론 해결을 할 수 없고 Manacher의 알고리즘을 이용하여야 합니다.

이 알고리즘은 배열에 현재 위치에서 가장 긴 팰린드롬의 길이를 저장함으로써 O(N) 만에 가장 긴 팰린드롬을 찾을 수 있는데 palin[i] -> i를 중심으로 길이가 가장긴 팰린드롬 길이의 절반값을 의미합니다.

 

이 과정을 거치기전에 짝수 길이 팰린드롬도 찾기 위하여 입력받는 문자열 양단에 #을 모두추가해주고 시작합니다.

 

maxlen이라는 변수에 i+palin[i] 값이 가장 큰 값을 유지시켜 주는데 즉 팰린드롬중 현재 가장 오른쪽 끝에 위치한 부분을 저장 하겠다는 의미입니다. 이 값을 저장 함으로써 다음 인덱스를 진행할때 그 인덱스가 이안에 포함 되있는지 안되있는지 여부에 따라 palin 값을 결정 할 수 있게 됩니다.

 

현재 maxlen에 들어있는 펠린드롬 내부에 지금 진행하는 인덱스가 포함 되어있다면 이때의 palin[i] 의 초기값은

min(palin[2*cur-i], maxlen-i) 이 값이 됩니다. 첫번째에 있는 값인 경우는 i와 대칭적 위치에 있는 palin의 값이 현재 maxlen의 펠린드롬을 초과하지 않는 경우 입니다. 초과하지 않는다면 이 값을 취하고 초과하게 된다면 maxlen-i 값( 이 값은 maxlen이 포함된 펠린드롬의 2*cur-i ~ i 까지의 펠린드롬 길이)을 취해주면 됩니다. 이후 그 이상의 문자들을 비교하여 palin 값을 정해주면 됩니다.

 

처음에 이해하기가 꽤나 힘들었습니다,, 문자열 관련 알고리즘은 역시 어려운 것 같습니다.

 

다음은 코드입니다.

 

#include <bits/stdc++.h>

using namespace std;

string str;
string astr;
int palin[200010];


void manachers() {

    //maxlen 은 위치+펠린드롬의 길이가 가장 긴 값 cur은 그때의 위치 인덱스
    int maxlen = 0, cur = 0;
    int len = astr.size();

    for(int i = 0; i < len; i++) {

        //현재 위치가 maxlen에 포함된 경우
        if(i <= maxlen) palin[i] = min(palin[2*cur-i], maxlen-i);
        else palin[i] = 0;

        int left = i-palin[i]-1;
        int right = i+palin[i]+1;
        while(left >= 0 && right < len && astr[left] == astr[right]) {
            palin[i]++;
            left = i-palin[i]-1;
            right = i+palin[i]+1;
        }

        if(maxlen < i+palin[i]) {
            maxlen = i+palin[i];
            cur = i;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> str;

    for(int i = 0; i < str.size(); i++) {
        astr+="#";
        astr+=str[i];
    }
    astr+="#";

    manachers();
    int ans = 0;
    for(int i = 0; i < astr.size(); i++) {
        ans = max(ans, palin[i]);
    }
    cout<<ans;

    return 0;
}