問題概要
英小文字からなる文字列 $S$ と長さ $3$ の英大文字からなる文字列 $T$ が与えれる．$S, T$ が次の条件を満たすかどうか，判定せよ*1
- $S$ の長さ $3$ の部分列であり，その各文字を大文字に変換したものが $T$ に一致する．
- $S$ の長さ $2$ の部分列であり，その各文字を大文字に変換したものの末尾に文字
Xを追加したものが $T$ に一致する．
部分列とは，元の列から $0$ 個以上の要素を削除して得られる列のことである．
制約
- $3 \leq |S| \leq 10^5$
解法
まずは，あまり本質的でない処理・条件分岐を消していきます．「大文字に変換し」というのは部分列をとる前の段階で予めやっておけば，判定時に考慮する必要が無くなります．これは，C++ では std::toupper で std::transform すればよく，Haskell では toUpper を map すればよいです．次に X を付与する件ですが，部分列の方ではなく，与えられた $S$ に予め付与しておくことで，長さ $3$ の部分列をとるケースに帰着できます．これらを行って得られる文字列を $S'$ とすれば，元の問題の代わりに
- $T$ は $S'$ の部分列か？
という問題を解けばよいことになります．
部分列かどうかの判定をするには，$T$ の各文字を順に $S'$ の文字に対応させていくことになります．より具体的には，$S'$ から得られた部分列の $j$ 文字目が $T_j$ に一致するように対応付けるということです．$T$ を基準に考えれば，$T$ を走査し，各文字について $S'$ の文字を（$S$ での出現順を崩さずに）対応させるということです．これをやるためには，
- $T_j$ を一致させるとき，$S'_i = T_j$ なる $i$ の内，最も小さい $i$ での $S'_i$ を一致させる．
という風にすればよいです．これでうまくいくことの直感的な説明としては，より大きい $i$ で対応付けたとすると後の選択肢が減って損をする（か，損をしなくても選択肢が増えることはない）ということになります．
上記から，実装すべきアルゴリズムとしては，
- $T$ の各文字 $T_i$ について順に，まだ対応付けていない $S$ の文字であって $T_i$ に一致するものの内，最も手前にあるものを対応付ける．
という処理を繰り返すものとなります．この処理が途中で失敗（対応付けるべき文字が存在しない）とき問題の出力は No で，そうでなければ Yes となります．これは，最後に対応付けた文字の位置を覚えておいて適切に更新することで実装できます．
計算量についてですが，$S$ の加工に $|S|$ 時間かかって，部分列を求めるときに $S'$ と $T$ の添字がそれぞれ最大 $|S'|$ 回・$|T|$ 回動くので，$O( |S| + |T| )$ 時間となります．
多数派にとっては余談かと思いますが，Haskell には isSubsequenceOf というそのまんまな関数があるので，実装コストを大幅に下げられます．
コード
int main() { IN( string, S, T ); transform( ALL( S ), begin( S ), []( const char c ){ return toupper( c ); } ); S += 'X'; int pos = 0; FOR( c, T ) { if ( ( pos = S.find( c, pos ) )++ == string::npos ) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0; }
main = getContents >>= putStrLn . which "Yes" "No" . uncurry ( flip isSubsequenceOf ) . ( ( ( ++ "X" ) . map toUpper ) *** id ) . mp . lines
