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; }