BOJ 25433 | PLCS

이걸 처음에 역추적까지 해야 한다고 생각해서 메모리 초과를 좀 많이 받았었는데 문제 난이도가 루비 V인 시점에서 눈치챘어야 했다;;

문자 $X$가 정확히 하나씩 존재한다는 걸 생각하면 문자열 $A$, $B$ 모두 $X$가 위치하는 부분에서 끊어서 나눌 수 있다.

$LCS(A, B)$ = $LCS(A_1, B_1)+LCS(A_2, B_2)$로 생각할 수 있기 때문에 Bitset LCS를 두 번 구해주면 된다.

$Y$에 대해서는 문자열 입력받을 때 문자 $Y$를 전부 제거해주는 전처리를 수행하면 된다.

$N$ 길이의 $LCS$가 존재한다는 것은 $1$~$N$ 사이의 모든 길이 $LCS$가 존재한다는 뜻이므로 소수를 구하는 건 나이브하게 해도 된다.

코드

#define private public
#include <bitset>
#undef private

#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define short unsigned short

#define debug if constexpr (local) std::cout
#define endl '\n'

// https://gist.github.com/cgiosy/a441de545c9e96b1d7b02cc7a00561f9?fbclid=IwAR0N3Woe8GwzAsxMapbEE9b7rrE_XArl50BRdQ9ZOTCxk-2X5BRrm-HBVpo
// Bitset Subtraction
template<size_t _Nw> void _M_do_sub(_Base_bitset<_Nw> &A, const _Base_bitset<_Nw> &B) {
	for(int i=0, c=0; i<_Nw; i++)
		c=_subborrow_u64(c, A._M_w[i], B._M_w[i], (unsigned long long*)&A._M_w[i]);
}
template<> void _M_do_sub(_Base_bitset<1> &A, const _Base_bitset<1> &B) {
	A._M_w-=B._M_w;
}
template<size_t _Nb> bitset<_Nb>& operator-=(bitset<_Nb> &A, const bitset<_Nb> &B) {
	_M_do_sub(A, B);
	return A;
}
template<size_t _Nb> inline bitset<_Nb> operator-(const bitset<_Nb> &A, const bitset<_Nb> &B) {
	bitset<_Nb> C(A);
	return C-=B;
}	

string a = "", b = "";
string result = "";

int LCS(string a, string b){
	bitset<50000> Match[26], x, B;
	for (int i = 0; i < b.length(); i++){
		Match[b[i]-97][i] = 1;
	}
	for (int i = 0; i < a.length(); i++){
		x = Match[a[i]-97] | B; B <<= 1; B |= 1;
		B = x ^ (x & (x-B));
	}
	
	return B.count();
}

bool isPrime(int N){
	for (int i = 2; i * i <= N; i++){
		if (N % i == 0) return false;
	}
	return true;
}

int findPrime(int N){
	while (!isPrime(N)){
		N--;
	}
	return N;
}

int main(){
	FASTIO;
	//ifstream cin("test.in");
	string oa, ob;
	cin >> oa >> ob;
	char x, y; cin >> x >> y;
	// remove y
	for (auto &i: oa){
		if (i != y) a += i;
	}
	for (auto &i: ob){
		if (i != y) b += i;
	}
	//debug << a << ' ' << a.length()-1 << ' ' << b << ' ' << b.length()-1 << endl;
	
	int rst = 0;
	int aidx = 0, bidx = 0;
	for (int i = 0; i < a.length(); i++){
		if (a[i] == x){
			aidx = i; break;
		}
	}
	for (int i = 0; i < b.length(); i++){
		if (b[i] == x) {
			bidx = i; break;
		}
	}
	
	rst += LCS(a.substr(0, aidx), b.substr(0, bidx));
	rst += LCS(a.substr(aidx, a.length()-aidx+1), b.substr(bidx, b.length()-bidx+1));
	
	if (rst < 2){
		cout << -1;
	}
	
	else cout << findPrime(rst);
}