백준 BOJ 10444 & 13275 - 가장 긴 팰린드롬 부분 문자열

마나커/마나허/manacher's 알고리즘을 구현하는 문제이다

똑같은 문제가 두개 있어서

깔끔하게 날먹했다.

 

www.acmicpc.net/problem/14444

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

www.acmicpc.net/problem/13275

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

마나허 알고리즘이 NYPC예선문제 풀때도 나왔었던거 같은데

그때는 마나허가 뭔지도 몰라서 그냥 틀렸었다.

이제 해결할수 있겠지?

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

int arr[234567];

void manacher(string s, int len){
    int rad=0;
	int cen=0; 
    for(int i=0; i<len; i++){
        if(i <= rad) arr[i] = min(rad-i, arr[2*cen-i]);
        else arr[i] = 0;
        
        while(i-arr[i]-1>=0 && i+arr[i]+1<len && s[i-arr[i]-1] == s[i+arr[i]+1]) arr[i]++;
        
        if( rad < i+arr[i]){
			rad = i+arr[i];
			cen = i;
		}
    }
}

int main(){
	int maxV=0;
	int maxP=0;
	string input, str;
    cin >> input;
    
	str += '.';
    for(int i=0; i<input.size(); i++){ str += input[i]; str += '.'; }
	
 	int len = str.size();
    manacher(str, str.size());
	
    for(int i=0; i<len; i++){
    	if(maxV < arr[i]){
    		maxV = arr[i];
    		maxP = i;
		}
	}
 	
    printf("%d\n", maxV);
 	//for(int i=maxP-maxV; i<=maxP+maxV; i++) if(str[i] != '.') printf("%c", str[i]);
    return 0;
}

주석쳐진 부분은 겨울학교 문제에서 추가로 요구하는 사항이었다.

흑흑흑 너무 어려워요 ㅠㅠ