[백준 22349] 가장 긴 공통 괄호 문자열

1. 풀이

 간단하게 접근을 시작하면 정답을 이분 탐색을 통해 찾을 수 있다. 일반적 이게 결정 문제 \(f(x)\)를 "\(x\)길이의 공통 괄호 부분 문자열이 존재하는가?" 로 정의한다.

그리고 각 \(A, B\) 문자열에서 \(x\) 길이의 연속한 부분 문자열을 올바른 괄호 문자열인지 확인한 다음 라빈 카프로 \(O(1)\)에 해싱한다. 해싱한 값을 가지고 있는 집합을 정렬한 뒤 이분 탐색을 통해 같은 해시 값들 동일한 괄호 문자열을 비교하여 해결해줄 수 있다.

 

 어떤 구간이 올바른 괄호 문자열인지 확인하는 방법은 먼저 \(( = 1, ) = -1\)으로 정의한다. 그리고 구간 합 \(psum\)을 정의한다. \([l, r]\) 부분 문자열이 괄호 문자열인 충분 조건은 아래와 같다. seg는 \(psum\)에 대한 min query를 하는 세그먼트 트리이다.

 1. \(psum_l = psum_r + 1\)

 2. seg query(l, r) >= \(psum_r\)

 그렇다면 query당 \(logN\)에 올바른 괄호 문자열인지 확인해줄 수 있다. 이 방법을 사용하면 여러 케이스에서 잘 작동하지만 "((()))((()))" 이런 형태가 정답인 경우 단조성이 성립하지 않아 제대로 된 정답을 구하지 못한다.

 

 그래서 결정 문제 \(f(x)\)를 수정하자. "\(x\)길이 이상의 공통 괄호 부분 문자열이 존재하는가?"로 정의하면 모든 케이스에서 단조성이 성립된다.

 각 과정에서 \(x\) 길이의 괄호 부분 문자열이 찾는 것이 아닌 \(x \)길이 이상의 괄호 부분 문자열을 찾으면 된다. 이 과정 또한 \(psum\)의 값이 나타나는 위치를 따로 기록해두면 이분 탐색을 통해 쉽게 찾아줄 수 있다. 왼쪽을 \(l\)이라 고정했을 때 \(psum_l - 1\)이 등장하는 위치를 기록한 배열을 \(V\)라 하면 \(V\)에서 이분 탐색으로 \(l+mid\) 이상인 위치를 찾아주면 된다.

 

 그리고 구간의 길이가 \(x\)로 일정하지 않기 때문에 투 포인터 비슷하게 라빈 카프를 해줄 수 없는 데, 이 부분에 대해서는 먼저 문자열을 라빈 카프로 해싱을 한 다음 구간 합 처럼 다룬다. 구간이 중간에 걸쳐 있는 경우에는 모듈러 값을 소수로 잡은 다음에 모듈러 인버스를 곱해주면 된다. 

 

 이후에 과정은 위에서 말한 방법과 동일하다. 생각 보다 과정이 많아 시간이 빡세다. 하지만 과정마다 전처리할 수 있는 부분이 꽤 있기 때문에 \(O(Nlog^2N)\)에 문제를 해결할 수 있다.

2. 소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
const ll key = 26;

string A, B;

ll pwKey[500001], invKey[500001], pA[500001], pB[500001];
ll nA[500001], nB[500001];
vector<int> posA[2*500001], posB[2*500001];

int f(char c) { return (c == ')'); }
ll mypow(ll x, ll cnt) {
	if (!cnt) return 1;
	if (cnt == 1) return x;
	ll mid = mypow(x, cnt/2);
	return (((mid * mid) % mod) * (cnt % 2 ? x : 1)) % mod;
}
ll invmod(ll x) { return mypow(x, mod - 2); }
ll Ahash(int l, int r) {
	l++, r++;
	return (((pA[r] - pA[l - 1] + mod)%mod) * invKey[l-1]) % mod;
}
ll Bhash(int l, int r) {
	l++, r++;
	return (((pB[r] - pB[l - 1] + mod) % mod) * invKey[l - 1]) % mod;
}

struct Segment {
	int n;
	vector<int> seg;
	void Init(int _n) {
		n = _n;
		seg.clear();
		seg.resize(4 * n, 1e9);
	}
	int update(int num, int s, int e, int idx, int diff) {
		if (idx < s || e < idx) return seg[num];
		if (s == e) return seg[num] = diff;
		int mid = s + e >> 1;
		return seg[num] = min(update(2 * num, s, mid, idx, diff), update(2*num+1, mid+1, e, idx, diff));
	}
	void update(int idx, int diff) { update(1, 0, n-1, idx, diff); }
	int query(int num, int s, int e, int l, int r) {
		if (r < s || e < l)return 1e9;
		if (l <= s && e <= r) return seg[num];
		int mid = s + e >> 1;
		return min(query(2*num, s, mid, l, r) ,query(2*num+1, mid+1, e, l, r));
	}
	int query(int l, int r) { return query(1, 0, n-1, l, r); }
}segA, segB;

struct Q {
	ll hash;
	int l, r;
};
bool operator<(const Q& a, const Q& b) {
	return a.hash < b.hash;
}

int off = 500000;

bool func(int mid) {
	vector<Q> vec;
	for (int i = 0; i < A.size(); i++) {
		int t = i + 2 * mid - 1;
		if (t >= A.size()) break; 
		if (A[i] == ')') continue;
		vector<int>& pos = posA[nA[i]-1+ off];
		int to = lower_bound(pos.begin(), pos.end(), t) - pos.begin();
		if (to == pos.size()) continue;

		if (segA.query(i, pos[to]) >= nA[i] - 1)
			vec.push_back({ Ahash(i, pos[to]), i , pos[to] });
	}
	sort(vec.begin(), vec.end());

	for (int i = 0; i < B.size(); i++) {
		int t = i + 2 * mid - 1;
		if (t >= B.size()) break;
		if (B[i] == ')') continue;
		vector<int>& pos = posB[nB[i]-1+ off];
		int to = lower_bound(pos.begin(), pos.end(), t) - pos.begin();

		if (to == pos.size()) continue;

		int l = i, r = pos[to];
		if (segB.query(l, r) < nB[i]-1) continue;

		ll h = Bhash(l, r);
		Q q; q.hash = h;
		int idx = lower_bound(vec.begin(), vec.end(), q) - vec.begin();
		for (int j = idx; j < vec.size() && vec[j].hash == h; j++) {
			Q& now = vec[j];

			if (r - l != now.r - now.l) continue;
			int d = r - l + 1;
			bool ans = true;
			for(int k=0; k < d; k++)
				if (B[l + k] != A[now.l + k]) { ans = false; break; }

			if (ans) return true;
		}
	}
	return false;
}

void solve() {
	cin >> A >> B;
	if (A.size() > B.size()) swap(A, B);

	segA.Init(A.size()); segB.Init(B.size());

	nA[0] = (A[0] == '(' ? 1 : -1);
	nB[0] = (B[0] == '(' ? 1 : -1);
	posA[nA[0]+ off].push_back(0);
	posB[nB[0]+ off].push_back(0);
	segA.update(0, nA[0]);
	segB.update(0, nB[0]);

	for (int i = 1; i <= A.size(); i++) {
		pA[i] = (pA[i - 1] + pwKey[i - 1] * f(A[i - 1])) % mod;
		if (i < A.size()) {
			nA[i] = (nA[i - 1] + (A[i] == '(' ? 1 : -1));
			segA.update(i, nA[i]);
			if (A[i] == ')') posA[nA[i]+ off].push_back(i);
		}
	}
	for (int i = 1; i <= B.size(); i++) {
		pB[i] = (pB[i - 1] + pwKey[i - 1] * f(B[i - 1])) % mod;
		if (i < B.size()) {
			nB[i] = (nB[i - 1] + (B[i] == '(' ? 1 : -1));
			segB.update(i, nB[i]);
			if (B[i] == ')') posB[nB[i]+ off].push_back(i);
		}
	}

	int ans = 0;
	int lo = 1, hi = A.size()/2;
	while (lo <= hi) {
		int mid = lo + hi >> 1;
		if (func(mid)) lo = mid + 1, ans = mid;
		else hi = mid - 1;
	}
	cout << 2*ans << "\n";

	for (int i = 0; i <= A.size(); i++) {
		pA[i] = 0;
		if (i < A.size()) {
			if (A[i] == ')') posA[nA[i]+ off].clear();
			nA[i] = 0;
		}
	}
	for (int i = 0; i <= B.size(); i++) {
		pB[i] = 0;
		if (i < B.size()) {
			if (B[i] == ')') posB[nB[i]+ off].clear();
			nB[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	pwKey[0] = 1;
	for (int i = 1; i <= 500000; i++) pwKey[i] = (key * pwKey[i - 1]) % mod;
	invKey[0] = 1;
	for (int i = 1; i <= 500000; i++) invKey[i] = mypow(pwKey[i], mod-2);

	int tc; cin >> tc;
	while (tc--) solve();

	return 0;
}