Overview

For each search query \(T\), we count how many bookshelves have at least one book whose title contains \(T\) as a subsequence. The subsequence check is performed efficiently using a two-pointer method that scans each title only once.

Analysis

Key Observations

• Subsequence checking can be done in \(O(|S|)\) by scanning the string \(S\) from left to right while sequentially looking for the next character of \(T\) to match.
  Example: \(T=\) "abc", \(S=\) "axbyc"

  • Find a → next look for b
  • Find b → next look for c
  • Find c → all matched (it is a subsequence)

• What we want is the number of bookshelves, not the number of books. So once at least one book in a bookshelf is a hit, there is no need to check the remaining books in that bookshelf (early termination is effective).

Why a Naive Approach is Dangerous

• If we perform subsequence checking using DP (e.g., \(dp[i][j]\)), it costs \(O(|S| \cdot |T|)\) per book. Since \(|S|, |T|\) can be up to 1000, a single check can take up to \(10^6\), and repeating this across many books and many queries will not fit within the time limit.
• On the other hand, the two-pointer method only costs \(O(|S|)\) per book, and since the total number of characters across all input strings is bounded by around \(10^5\), this remains practical even with up to \(Q \le 200\) queries.

How to Solve It

• For each query \(T\):
  • Iterate over each bookshelf:
    • For each title \(S\) in the bookshelf, use the two-pointer method to check whether \(T\) is a subsequence of \(S\)
    • If even one book matches, count that bookshelf and move on to the next bookshelf (early termination)
• Additionally, when \(|T| > |S|\), \(T\) can never be a subsequence of \(S\), so we skip the check to avoid unnecessary work.

Algorithm

1. Read the input and store titles as an array of strings for each bookshelf.
2. Prepare a subsequence checking function is_subseq(T, S) (two-pointer method):
   • Maintain an index \(i = 0\) for \(T\)
   • Scan \(S\) from left to right; when a character of \(S\) matches \(T[i]\), increment \(i\)
   • If \(i == |T|\), all characters have been matched, so return True
   • If we reach the end of \(S\) without matching all characters, return False
3. For each query \(T\), do the following:
   • cnt = 0
   • For each bookshelf, check titles one by one; if is_subseq(T, S) is True for any book, do cnt += 1 and move to the next bookshelf (break)
4. Output cnt for each query.

Complexity

• Time complexity: At most \(O\!\left(Q \cdot \sum |S|\right)\)
  (The upper bound is scanning all titles once per query. If a hit occurs within a bookshelf, it will be less than this.)
• Space complexity: \(O\!\left(\sum |S| + \sum |T|\right)\)
  (For storing the input strings)

Implementation Notes

• Two-pointer subsequence check: It only scans \(S\) once, making it fast.

• Length check for pruning: Only call the check function when \(|T| \le |S|\) to avoid unnecessary work.

• Early termination per bookshelf: Once one book is a hit, that bookshelf is confirmed, so skip the remaining titles (break).

• Fast I/O: Using sys.stdin.buffer.read().split() and handling strings as bytes makes comparisons faster.

  Source Code

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()

This editorial was generated by gpt-5.2-high.