BOJ 32030 두 배

문제 링크입니다.

관찰

어떻게 타이핑을 하든 문자열의 맨 뒤에만 영향을 줄 수 있습니다. 그러니 앞쪽을 원하는 문자열에 맞게 만들어주고 나서 그 부분은 고정했다고 생각해 줄 수 있습니다. 어차피 목표 문자열과 안 맞는 부분이 생기면 그 부분까지는 다 지워야 합니다. 이제 다음과 같이 D를 정의합시다.

D[i] : 정확히 문자열의 i번째 문자까지 타이핑하는 데 필요한 최소 입력 수 (i를 0-based로 쓰겠습니다.)

자명하게 D[0] = 1입니다.

입력 변형하기

i번째 글자까지 맞게 입력한 상황에서, 할 수 있는 행동은 다음 세 가지입니다.

• 맨 뒷 글자 삭제하기
• “두 배” 되지 않는 경우, i+1번째 글자 입력하기
• i+1번째 글자 == 1번째 글자라면, “두 배” 되는 글자 입력하기

첫 두 종류의 행동은 가중치 1의 한 칸 앞이나 뒤로 가는 간선으로 표현할 수 있습니다.

세 번째 행동은 “두 배” 된 문자열이 목표 문자열과 얼마나 겹치는 지 확인하고, 맞지 않는 부분을 제거해 주어야 합니다.

공통 접두사 길이 계산하기

이를 위해 문자열의 각 자리마다 전체 문자열의 접두사면서 그 자리에서 시작하는 문자열의 접두사이기도 한 문자열의 최장 길이를 구해 둘 것입니다.

Z 알고리즘은 정확히 이러한 작업을 선형 시간에 수행해 줍니다. KMP를 이용해서도 비슷한 작업을 할 수 있습니다.

답 구하기

세 종류의 간선으로 이루어진 그래프의 0번 정점에서 (N-1)번 정점으로의 최단 경로를 구하는 문제로 환원되었습니다. 이제 다익스트라를 돌려주기만 하면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<int> Z(string s){
	int n = s.size(), l = -1, r = -1;
	vector<int> z(n); z[0] = n;
	for(int i = 1; i < n; i++){
		if(i <= r) z[i] = min(z[i-l], r-i+1);
		while(i+z[i] < n && s[i+z[i]] == s[z[i]]) z[i]++;
		if(i+z[i]-1 > r) l = i, r = i+z[i]-1;

	}
	return z;
}

bool c[26][26], jump[26];
ll d[505050];
priority_queue<pll> pq;
vector<pll> e[505050];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; string a, b; cin >> n >> a >> b;
	for(int i = 0; i < n; i++){
		c[a[i]-'a'][b[i]-'a'] = jump[a[i]-'a'] = 1;
	}
	string s; cin >> s; auto z = Z(s); n = s.size();
	
	for(int i = 1; i < n; i++){
		e[i].push_back({-1, i-1});
		if(!c[s[i-1]-'a'][s[i]-'a']) e[i-1].push_back({-1, i});
		if(jump[s[i-1]-'a']){
			int nxt = i-1+z[i];
			if(nxt > 2*(i-1)){
				if(c[s[i-1]-'a'][s[2*i]-'a']) nxt = 2*i;
				else nxt = 2*i-1;
			}
			e[i-1].push_back({-(1+2*i-nxt), nxt});
		}
	}
	
	memset(d, 0x3F, sizeof(d));
	d[0] = 1; pq.push({-1,0});
	while(pq.size()){
		auto [w, now] = pq.top(); pq.pop();
		if(d[now] < -w) continue;
		for(auto [nw, nxt] : e[now]){
			if(d[nxt] > -w-nw){
				d[nxt] = -w-nw;
				pq.push({w+nw, nxt});
			}
		}
	}
	if(d[n-1] == d[n]) cout << -1;
	else cout << d[n-1];
}