Codeforces Beta Round #25 (Div. 2 Only) E : Test

問題概要

3つの文字列がある。全ての文字列を部分文字列に含むような最小の文字列の長さを求める問題。文字列長<10^5。

解法

まず他の文字列に含まれる文字列は消す。その後、Z-algorithmでA-B, B-Cについてlongest prefixを求め、その分をA+B+Cから引く。順番についてnext_permutationで全部試す。

acceptされたコード

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = (int)(1.05e9);

void buildLongestPrefixMatch(const char* str, vector<int>& Z){
	const int len = strlen(str);
	Z.assign(len, 0);
	for (int i = 1, left = 0, right = 0; i < len; ++i) {
		if ( i <= right ) {
			Z[i] = min(right - i + 1, Z[i-left]);
		}
		for (; i+Z[i] < len && str[Z[i]] == str[i+Z[i]]; ++Z[i]) ;
		if (i + Z[i] - 1 > right) {
			left = i;
			right = i + Z[i] - 1;
		}
	}
}

template<typename numType>
inline bool updateMin(numType& lhs, const numType& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}

template<typename numType>
inline bool updateMax(numType& lhs, const numType& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}

vector<string> strs;

void init() {
	strs.resize(3);
	for (int i = 0; i < 3; ++i) {
		cin >> strs[i];
	}
}

int subSolve() {
	const int L0 = strs[0].length(), L1 = strs[1].length(), L2 = strs[2].length();
	int ans = L0 + L1 + L2;

	string B_A = strs[1] + '$' + strs[0];
	vector<int> Z_ba;
	buildLongestPrefixMatch(B_A.c_str(), Z_ba);

	int maxi = 0;
	for (int i = L1 + 1; i < L0 + L1 + 1; ++i) {
		if (Z_ba[i] == min(L1, L0 + L1 + 1 - i)) {
			updateMax(maxi, Z_ba[i]);
		}
	}
	ans -= maxi;

	string C_B = strs[2] + '$' + strs[1];
	vector<int> Z_cb;
	buildLongestPrefixMatch(C_B.c_str(), Z_cb);

	maxi = 0;
	for (int i = L2 + 1; i < L2 + L1 + 1; ++i) {
		if (Z_cb[i] == min(L2, L2 + L1 + 1 - i)) {
			updateMax(maxi, Z_cb[i]);
		}
	}
	ans -= maxi;
	return ans;
}

int solve() {
	int ans = INF;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) if (i != j) {
			string s = strs[i] + '$' + strs[j];
			int L0 = strs[i].length(), L1 = strs[j].length();
			vector<int> Z;
			buildLongestPrefixMatch(s.c_str(), Z);
			for (int k = L0; k < L0 + L1 + 1; ++k) {
				if (Z[k] == L0) {
					strs[i] = strs[j];
					break;
				}
			}
		}
	}
	sort(strs.begin(), strs.end());
	do {
		updateMin(ans, subSolve());
	} while( next_permutation(strs.begin(), strs.end()));
	return ans;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}