概要

各文字列が sayounara を部分列として含むかどうかを判定する問題です。部分列とは、元の文字列から文字を飛び飛びに（順序を保って）取り出して作れる文字列のことです。

考察

部分列の判定とは

部分列の判定は、「ターゲット文字列の各文字を、元の文字列の中で左から順に見つけられるか？」という問題に帰着できます。

例えば、文字列 sxxxaxyzoounara に対して sayounara が部分列として含まれるか確認するには：

1. s を探す → 1文字目の s が一致 ✓
2. a を探す → 5文字目の a が一致 ✓
3. y を探す → 7文字目の y が一致 ✓
4. o を探す → 9文字目の o が一致 ✓
5. … 以下同様に最後の a まで全て見つかれば Yes

このように、ターゲット文字列の先頭から1文字ずつ順番に、元の文字列を左から走査して一致する文字を探す貪欲法（グリーディ）が最適です。

なぜ貪欲法で正しいのか

ターゲットの各文字をできるだけ早い位置でマッチさせることで、残りの文字列に余裕を持たせることができます。これにより、マッチの機会を逃すことがありません。

素朴なアプローチとの比較

「部分列」と聞くと、全ての取り出し方を列挙したくなるかもしれませんが、それは指数的な計算量になり TLE になります。上記の貪欲法なら、元の文字列を1回走査するだけで判定できます。

アルゴリズム

各文字列 \(S_i\) に対して、以下の手順で判定します：

1. ターゲット target = "sayounara" のポインタ \(j\) を \(0\) に初期化する。
2. \(S_i\) の各文字 \(c\) を左から順に見る。
   • もし \(c\) が target[j] と一致すれば、\(j\) を \(1\) 進める。
   • \(j\) が target の長さ（\(9\)）に達したら、部分列として含まれているので Yes。
3. \(S_i\) を最後まで見ても \(j\) が \(9\) に達しなければ No。

計算量

• 時間計算量: \(O\left(\displaystyle\sum_{i=1}^{N} |S_i|\right)\)
  • 各文字列を1回走査するだけなので、全文字列の長さの合計に比例します。制約より合計は最大 \(5 \times 10^6\) なので十分高速です。
• 空間計算量: \(O\left(\max |S_i|\right)\)
  • 各文字列を読み込む分の領域が必要です。出力バッファを含めても \(O(N + \max |S_i|)\) です。

実装のポイント

• 高速な入力: 文字列の合計長が最大 \(5 \times 10^6\) と大きいため、Python では sys.stdin.readline を使って入力を高速化しています。標準の input() では TLE になる可能性があります。

• 出力のまとめ書き: 毎回 print するのではなく、結果をリストに溜めて最後に '\n'.join(out) で一括出力することで、I/O のオーバーヘッドを削減しています。

• rstrip() の使用: readline() は末尾に改行文字を含むため、.rstrip() で除去してから判定を行います。これを忘れると、改行文字がマッチ処理に影響する可能性があります。

• 早期終了: ターゲット文字列の全文字がマッチした時点（\(j = 9\)）で即座に True を返し、残りの文字列の走査を省略しています。

  ソースコード

import sys
input = sys.stdin.readline

def check(s):
    target = "sayounara"
    j = 0
    for c in s:
        if c == target[j]:
            j += 1
            if j == len(target):
                return True
    return False

N = int(input())
out = []
for _ in range(N):
    s = input().rstrip()
    out.append("Yes" if check(s) else "No")
print('\n'.join(out))

---

この解説は claude4.6opus-thinking によって生成されました。