Codeforces Round #138 (Div. 1) B : Two Strings

問題概要

文字列S,T(長さ<2e5)の文字列が与えられる。Tに等しいSの部分列でSが全て被覆できるかどうか判定する問題。

解法

Sの各文字について、その文字は部分列Tのk番目になれる、の最大のkを計算しておく。ついでに、後ろから見たものも計算しておく。後は前から見たときと後ろから見たときでその文字を含む部分列=Tが存在するかどうかが判定できる。

acceptされたコード

あんまり実装が賢くない…。

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

const int MAX_L = int(2e5);
const int INF = int(1.05e9); 
char S[MAX_L + 1], T[MAX_L + 1];
vector<int> appears[26];

void init() {
	scanf(" %s %s ", S, T);
}

bool solve() {
	const int Slen = strlen(S), Tlen = strlen(T);

	static int longestMatch[2][MAX_L + 1];
	for (int k = 0; k < 2; ++k) {
		static int nextChar[MAX_L] = {0};
		for (int i = 0; i < 26; ++i) {
			appears[i].clear();
		}
		for (int i = 0; i < Tlen; ++i) {
			appears[int(T[i] - 'a')].push_back(i);
		}
		for (int i = 0; i < 26; ++i) {
			for (int j = 0; j < int(appears[i].size()); ++j) {
				nextChar[appears[i][j]] = j + 1 < int(appears[i].size()) ? appears[i][j+1] : Tlen;
			}
		}

		int last[26];
		memset(last, -1, sizeof(last));
		for (int i = 0; i < Slen; ++i) {
			const int cur = S[i] - 'a';
			if (appears[cur].empty()) {
				return false;
			}
			const int curPos = last[cur];
			const int nxtPos = curPos == -1 ? appears[cur][0] :nextChar[curPos];
			if (nxtPos == Tlen) {
				longestMatch[k][i] = curPos;
				continue;
			}
			bool ok = find(last, last + 26, nxtPos - 1) != last + 26;
			if (ok) {
				last[cur] = nxtPos;
			}
			longestMatch[k][i] = (ok ? nxtPos : curPos);
		}
		reverse(S, S+Slen);
		reverse(T, T+Tlen);
	}

	for (int i = 0; i < Slen; ++i) {
		if (longestMatch[0][i] + longestMatch[1][Slen - 1 - i] < Tlen - 1) {
			return false;
		}
	}

	return true;
}

int main() {
	init();
	puts(solve() ? "Yes" : "No");
	return 0;
}