BOJ(백준) 25582번 pqbd

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

25582번: pqbd

문제에 나오는 거울 대칭과 점 대칭은 일종의 특수한 조건의 펠린드롬이라고 이해할 수 있다.

그래서 부분 문자열 최장 펠린드롬 알고리즘을 살짝 수정하여 점 대칭과 거울 대칭 각각의 최대 길이를 구하고 둘 중에 큰값을 출력하면 되는 문제이다.

 

그러나 N<=500000이므로 O(N^2)의 시간이 걸리는 2차원 dp 방식은 tle가 나온다.

따라서 O(N)의 시간에 펠린드롬의 개수, 길이, 위치 등을 찾을 수 있는 알고리즘인 매내처(manacher) 알고리즘을 사용해야 된다.

 

매내처 알고리즘의 원리 간단히 알아보자.

0	1	2	3	4	5	6	7	8	9
d	a	b	a	c	a	b	a	c	d

 

위와 같은 문자열이 있다고 생각해보자 윗 줄은 인덱스 아랫 줄은 각 인덱스에 해당하는 문자이다.

0	1	2	3	4	5	6	7	8	9
d	a	b	a	c	a	b	a	c	d

 

길이가 1인 펠린드롬을 제외하고 문자열을 앞에서부터 각각의 인덱스를 중심으로 하는 펠린드롬을 찾아보면 2번 인덱스를 중심으로 길이가 3인 펠린드롬의 존재를 확인할 수 있다.

0	1	2	3	4	5	6	7	8	9
d	a	b	a	c	a	b	a	c	d

 

그 뒤로 계속 찾아보면 4번 인덱스를 중심으로 길이가 7인 펠린드롬의 존재를 확인할 수 있다.

0	1	2	3	4	5	6	7	8	9
d	a	b	a	c	a	b	a	c	d

 

또 다시 계속 찾아보면  6번 인덱스를 중심으로 길이가 5인 펠린드롬의 존재를 확인할 수 있다.

 

위에서 본 3가지 회문의 길이를 판별하는 데에 각각 몇번의 연산이 필요할까?

첫번째는 인덱스 1과 3, 0과 4를 비교해야하므로 2번,

두번째는 인덱스 3과 5, 2와 6, 1과 7, 0과 8을 비교해야하므로 4번,

세번째는 인덱스 5와 7, 4와 8, 3과 9를 비교해야하므로 3번이 필요하다고 생각할 수 있다.

 

과연 이게 최선일까? 놀랍게도 세번째는 2번의 연산만으로도 충분하다.

0	1	2	3	4	5	6	7	8	9
d	a	b	a	c	a	b	a	c	d

 

우리는 1~3번 인덱스가 회문이고 1~7번 인덱스가 회문인 것을 이미 알고 있었다.

그러므로 4번을 중심으로 1~3번 인덱스와 5~7번 인덱스는 대칭을 이루는데

1~3번 인덱스가 회문이므로 5~7번 인덱스 또한 회문인 것을 즉시 알 수 있다.

따라서 우리는 6번 인덱스를 중심으로한 최대 길이의 펠린드롬을 찾을 때 5와 7번을 비교하는 연산을 건너뛰고 바로 4번과 8번부터 비교를 시작해도 된다.

 

이러한 원리를 이용한 것이 바로 매내처 알고리즘이다.

 

다만 이러한 방식은 길이가 짝수인 펠린드롬을 판별하는 것이 불가능하므로 문자열의 각 문자 사이에 공백을 넣어 모든 펠린드롬의 길이를 홀수로 만든 뒤 알고리즘을 적용해야 된다.

 

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;
}