C - Airport Code 解説 by en_translator
Let \(S_i\) denote the \(i\)-th character of \(S\), and \(T_j\) the \(j\)-th character of \(T\).
First of all, capitalize all characters of \(S\).
If \(T\) does not end with X
, one can determine if \(T\) is a substring of \(S\).
If \(T\) ends with X
, one can determine if the first two characters of \(T\) is a substring of \(S\).
Finally, we describe how to determine if a string \(T\) is a substring of \(S\). This can be achieved by corresponding each character of \(T\) to a character of \(S\), greedily from the left, and checking if it succeeds to the end of \(T\). More formally, it can be determined by the following greedy algorithm:
- Initialize \(k\leftarrow 1\).
- For each \(j=1,2,\dots,|T|\), do the following:
- If there is no \(i\) such that \(S_i=T_j\) and \(k \leq i \leq |S|\), return
No
and terminate. - If there is a conforming \(i\), let \(i'\) be the smallest one. Set \(k \leftarrow i' + 1\).
- If there is no \(i\) such that \(S_i=T_j\) and \(k \leq i \leq |S|\), return
- Return
Yes
and terminate.
Sample code (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")
投稿日時:
最終更新: