BOJ(백준) 25582번 pqbd

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

문제에 나오는 거울 대칭과 점 대칭은 일종의 특수한 조건의 펠린드롬이라고 이해할 수 있다. 그래서 부분 문자열 최장 펠린드롬 알고리즘을 살짝 수정하여 점 대칭과 거울 대칭 각각의 최대 길이를 구하고 둘 중에 큰값을 출력하면 되는 문제이다.

그러나 N<=500000이므로 O(N^2)의 시간이 걸리는 2차원 dp 방식은 tle가 나온다. 따라서 O(N)의 시간에 펠린드롬의 개수, 길이, 위치 등을 찾을 수 있는 알고리즘인 매내처(manacher) 알고리즘을 사용해야 된다.

AC code

#include <bits/stdc++.h>

using namespace std;
int psym[200],msym[200],arr[1000001],mtr[1000001],len,mx; //psym과 msym은 대칭 문자로의 매핑을 위한 배열, mtr은 각 인덱스를 중심으로한 최장 펠리드롬의 길이 
string s;
string mchar="pqdbiimmvvwwllooxx",pchar="llooxxpdbqunsszz"; //대칭쌍 전처리

void manacher(int sym[],string chars)
{
    int r=0,p=0;
    for(int i=0;i<chars.length();i+=2) {
        sym[chars[i]]=chars[i+1];
        sym[chars[i+1]]=chars[i];
    }
    for(int i=0;i<2*len+1;i++) {
		if(r>i) mtr[i]=min(mtr[2*p-i],r-i);
        else mtr[i]=0;
		if(!arr[i]||sym[arr[i]]==arr[i]) while(sym[arr[i-mtr[i]-1]]==arr[i+mtr[i]+1]&&i-mtr[i]-1>=0&&i+mtr[i]+1<2*len+1) mtr[i]++;
		if(i+mtr[i]>r) r=i+mtr[p=i];
		mx=max(mtr[i],mx);
	}
}

int main()
{
	cin>>s;
	len=s.length();
	for(int i=0;i<len;i++) arr[2*i+1]=s[i];
    manacher(msym,mchar);
    manacher(psym,pchar);
	if(!mx) cout<<"NOANSWER";
	else cout<<mx;
}