Official
C - Airport Code Editorial
by
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\) のできるだけ左の方から対応させていって, すべて対応させられるか判定すればよいです. より形式的には,次のような貪欲法により判定できます.
- \(k\leftarrow 1\) と初期化する
- \(j=1,2,\dots,|T|\) の順に,以下を行う:
- \(S_i=T_j\) かつ \(k \leq i \leq |S|\) を満たす \(i\) が存在しなければ,
No
を返して終了する. - 条件を満たす \(i\) が存在すれば,そのうち最小のものを \(i'\) とする. \(k \leftarrow i' + 1\) と更新する.
- \(S_i=T_j\) かつ \(k \leq i \leq |S|\) を満たす \(i\) が存在しなければ,
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: