Official

C - Airport Code Editorial by sotanishy


\(S\)\(i\) 文字目を \(S_i\) と表します.同様に, \(T\)\(j\) 文字目を \(T_j\) と表します.

あらかじめ, \(S\) の文字をすべて英大文字に変換しておきます.

\(T\) の最後の文字が X でない場合, \(T\)\(S\) の部分列であるかどうか判定すればよいです.

\(T\) の最後の文字が X である場合, \(T\) の最初の2文字が \(S\) の部分列であるかどうか判定すればよいです.

最後に,文字列 \(T\) が文字列 \(S\) の部分列であるかの判定方法を述べます. これは, \(T\) の各文字を \(S\) のできるだけ左の方から対応させていって, すべて対応させられるか判定すればよいです. より形式的には,次のような貪欲法により判定できます.

  1. \(k\leftarrow 1\) と初期化する
  2. \(j=1,2,\dots,|T|\) の順に,以下を行う:
    1. \(S_i=T_j\) かつ \(k \leq i \leq |S|\) を満たす \(i\) が存在しなければ, No を返して終了する.
    2. 条件を満たす \(i\) が存在すれば,そのうち最小のものを \(i'\) とする. \(k \leftarrow i' + 1\) と更新する.
  3. Yes を返して終了する.

実装例 (Python)

def check(S, T):
    i = 0
    for t in T:
        while i < len(S) and S[i] != t:
            i += 1
        if i == len(S):
            return False
        i += 1
    return True

S = input().upper()
T = input()
print("Yes" if check(S, T if T[-1] != "X" else T[:-1]) else "No")

posted:
last update: