概要

各検索クエリ \(T\) について、「\(T\) を部分列として含むタイトルを1冊以上持つ本棚」が何個あるかを数えます。部分列判定は各タイトルを1回なめるだけの二点法（ポインタ法）で高速に行います。

考察

重要な観察

• 「部分列（subsequence）」判定は、文字列 \(S\) を左から見ながら \(T\) の次に一致させたい文字を順に探すことで、\(O(|S|)\) でできます。
  例：\(T=\) "abc", \(S=\) "axbyc"

  • a を見つける → 次は b
  • b を見つける → 次は c
  • c を見つける → すべて一致（部分列）

• 求めたいのは「本の冊数」ではなく「本棚の数」なので、ある本棚内で1冊でもヒットしたら、その本棚についてはそれ以上調べる必要がありません（早期打ち切りが効く）。

素朴なアプローチが危険な理由

• 部分列判定を DP（\(dp[i][j]\) など）で行うと、1冊あたり \(O(|S|\cdot|T|)\) になり、\(|S|,|T|\) が最大 1000 なので1回で最大 \(10^6\)、これを多数の本・多数のクエリで繰り返すと間に合いません。
• 一方で二点法なら1冊あたり \(O(|S|)\) で済み、入力全体の文字数が \(10^5\) 程度に抑えられているため、クエリ数 \(Q \le 200\) でも現実的な計算量に収まります。

どう解決するか

• 各クエリ \(T\) について、
  • 各本棚を見て、
    • 本棚内の各タイトル \(S\) に対し二点法で「\(T\) が \(S\) の部分列か」を判定
    • 1冊でも真ならその本棚はカウントし、次の本棚へ（早期終了）
• さらに \(|T| > |S|\) のときは絶対に部分列にならないので、判定前に弾いて無駄を減らします。

アルゴリズム

1. 入力を読み込み、本棚ごとにタイトル文字列の配列として保持する。
2. 部分列判定関数 is_subseq(T, S) を用意する（二点法）：
   • \(T\) 側のインデックス \(i=0\) を持つ
   • \(S\) を左から順に見て、\(S\) の文字が \(T[i]\) と一致したら \(i\) を1進める
   • \(i==|T|\) になったら全て一致したので True
   • 最後まで見ても揃わなければ False
3. 各クエリ \(T\) について以下を実行：
   • cnt = 0
   • 各本棚について、タイトルを順に調べ、1冊でも is_subseq(T, S) が True なら cnt += 1 して次の本棚へ（break）
4. 各クエリの cnt を出力する。

計算量

• 時間計算量: 最大で \(O\!\left(Q \cdot \sum |S|\right)\)
  （各クエリごとに、全タイトルを一度ずつなめるのが上限。途中で本棚内ヒットが出ればそれより減る）
• 空間計算量: \(O\!\left(\sum |S| + \sum |T|\right)\)
  （入力文字列を保持する分）

実装のポイント

• 二点法で部分列判定：\(S\) を1回走査するだけなので高速です。

• 長さチェックで枝刈り：\(|T| \le |S|\) のときだけ判定関数を呼ぶと無駄が減ります。

• 本棚単位で早期終了：1冊ヒットしたらその本棚は確定なので、残りのタイトルを見ない（break）。

• 高速入出力：sys.stdin.buffer.read().split() を使い、文字列は bytes のまま扱うと比較が速くなります。

  ソースコード

import sys


def is_subseq(t: bytes, s: bytes) -> bool:
    m = len(t)
    if m > len(s):
        return False
    i = 0
    ti = t[0]
    for ch in s:
        if ch == ti:
            i += 1
            if i == m:
                return True
            ti = t[i]
    return False


def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    shelves = []
    for _ in range(N):
        k = int(next(it))
        titles = [next(it) for _ in range(k)]  # bytes
        shelves.append(titles)

    Q = int(next(it))
    queries = [next(it) for _ in range(Q)]  # bytes

    sub = is_subseq
    out_lines = []
    for t in queries:
        cnt = 0
        lt = len(t)
        for titles in shelves:
            hit = False
            for s in titles:
                if lt <= len(s) and sub(t, s):
                    hit = True
                    break
            if hit:
                cnt += 1
        out_lines.append(str(cnt))

    sys.stdout.write("\n".join(out_lines))


if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。