公式

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:

  1. Initialize \(k\leftarrow 1\).
  2. For each \(j=1,2,\dots,|T|\), do the following:
    1. If there is no \(i\) such that \(S_i=T_j\) and \(k \leq i \leq |S|\), return No and terminate.
    2. If there is a conforming \(i\), let \(i'\) be the smallest one. Set \(k \leftarrow i' + 1\).
  3. 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")

投稿日時:
最終更新: