BOJ 14755 Pseudoknot

문제 링크입니다.

문제 요약

다음의 표기를 약속합시다.

• 문자열 $S$에 대해 $rev(S)$는 $S$를 뒤집은 문자열입니다.

주어진 문자열 $S$를, 빈 문자열이 아닌 두 문자열 $u,v$와 비어 있을 수도 있는 두 문자열 $x, y$에 대해 $u,x,rev(v), rev(u),y,v$를 이 순서대로 이어붙인 형태로 표현하려 합니다.

$\min(\vert u \vert, \vert v \vert)$의 최댓값을 구하세요.

풀이

목표로 하는 답의 값 $m$을 정해 놓고 “$u$와 $v$의 길이를 각각 $m$ 이상으로 해가 존재하는가?”를 문제로 두면 이는 결정 문제이므로, 이분 탐색을 통해 원래 얻고자 했던 최적화 문제의 답을 얻을 수 있습니다.

정해진 $m$에 대해 문제를 해결하는 방법을 생각해 봅시다. $rev(v)$와 $rev(u)$가 $S$ 안에서 서로 붙어있어야 함으로부터, 두 문자열의 방향이 서로 반대라고 생각하면 두 문자열 $rev(u)$와 $rev(v)$가 같은 시작점을 갖는다고 생각할 수 있습니다. 이 상황에서 두 문자열의 길이를 각각 $m$ 이상인 선에서 최대한 짧게 만드는 것이 우리의 목적입니다.

$u$와 $v$는 각각 (한쪽 문자열을 반대 방향으로 돌려서 생각하면) 문자열의 접두사로 생각할 수 있습니다. 따라서 KMP를 이용해 각 위치에서 접두사와 겹치는 가장 긴 패턴을 찾고, 이를 $m$ 이상인 선에서 실패 함수를 따라가면서 줄여나가는 방식으로 각 인덱스에 대해 최소의 $u$와 $v$의 길이를 구할 수 있습니다…만. 그냥 실패 함수를 쓰면 최악의 경우에 한 번의 결정 문제를 해결하는 데에 ${\cal O}(N^2)$의 시간 복잡도가 필요합니다.

이를 해소하기 위해 실패 함수의 희소 배열을 구축한다는 발상을 할 수 있습니다. 이를 바탕으로 하면 각 인덱스에서 필요한 길이의 패턴을 찾는 데에 ${\cal O}(\lg N)$의 시간 복잡도가 필요하므로, 하나의 결정 문제를 ${\cal O}(N \lg N)$에 해결할 수 있고, 따라서 최적화 문제를 ${\cal O}(N \lg^2 N)$에 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
string s;
int fa[20][202020], fb[20][202020], ka[202020], kb[202020], n;

bool solve(int len){
	if(!len) return 1;
	for(int i = 1; i < n; i++){
		int A = ka[n-1-i], B = kb[i-1];
		if(A < len || B < len) continue;
		A--; B--;
		for(int bit = 19; bit >= 0; bit--){
			if(fa[bit][A] >= len) A = fa[bit][A]-1;
			if(fb[bit][B] >= len) B = fb[bit][B]-1;
		}
		A++; B++;
		//cout << i << ' ' << A << ' ' << B << '\n';
		if(A+B <= min(i, n-i)) return 1;
	}
	return 0;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> s; n = s.size();
	for(int i = 1, j = 0; i < n; i++){
		while(j > 0 && s[i] != s[j]) j = fa[0][j-1];
		if(s[i] == s[j]) fa[0][i] = ++j;
	}
	for(int i = 1, j = 0; i < n; i++){
		while(j > 0 && s[n-1-i] != s[n-1-j]) j = fb[0][j-1];
		if(s[n-1-i] == s[n-1-j]) fb[0][i] = ++j;
	}
	
	for(int bit = 1; bit < 20; bit++) for(int i = 1; i < n; i++){
		if(fa[bit-1][i] > 0) fa[bit][i] = fa[bit-1][fa[bit-1][i]-1];
		if(fb[bit-1][i] > 0) fb[bit][i] = fb[bit-1][fb[bit-1][i]-1];
	}
	
	for(int i = 0, j = 0; i < n; i++){
		while(j > 0 && s[n-1-i] != s[j]) j = fa[0][j-1];
		if(s[n-1-i] == s[j]) ka[i] = ++j;
	}
	for(int i = 0, j = 0; i < n; i++){
		while(j > 0 && s[i] != s[n-1-j]) j = fb[0][j-1];
		if(s[i] == s[n-1-j]) kb[i] = ++j;
	}
	int l = 0, r = n;
	while(l < r){
		int mid = l+r>>1;
		if(solve(mid)) l = mid+1;
		else r = mid;
	}
	if(l == 1) cout << -1;
	else cout << l-1;
}