Overview

Given the titles of books on each bookshelf, determine whether any title contains the search query string as a subsequence, and count the number of matching bookshelves.

Analysis

In this problem, we need to repeatedly determine “Is string \(T\) a subsequence of string \(S\)?” Being a subsequence means that \(T\) can be obtained by deleting some characters from \(S\) (while preserving the order of the remaining characters).

For example, for S = "abcde", T = "ace" is a subsequence because a, c, e appear in order.

Naive Approach and Its Issues

A straightforward approach would be to perform subsequence checking for every query against all bookshelves and all book titles. Looking at the constraints:

• Up to \(N = 100\) bookshelves
• Up to several thousand books per bookshelf (up to \(5000\) books in total)
• Up to \(Q = 200\) queries

A brute-force approach may be fast enough. However, it may not pass if the subsequence checking is not implemented efficiently.

Efficient Subsequence Checking

In Python, you can efficiently check for subsequences using the combination of iter() and all(c in it for c in t). This method uses an iterator to check whether characters are found in order from the beginning. Since it only looks at positions after the last matched one, it correctly performs subsequence checking.

With this implementation, a single subsequence check runs in \(O(|S|)\) time.

Algorithm

1. First, read all input and store the list of book titles for each bookshelf.
2. For each search query \(T\), do the following:
   • For each bookshelf, determine whether any title in it contains \(T\) as a subsequence.
   • If at least one title matches, that bookshelf is counted.
3. Output the number of matching bookshelves for each query.

Subsequence checking is performed efficiently using the iterator-based method for fast execution.

Complexity

• Time complexity: \(O(Q \cdot N \cdot K_{\text{avg}} \cdot (|S|_{\text{avg}} + |T|))\)
  • For each query, subsequence checking is performed across all bookshelves and all titles.
  • A single subsequence check takes \(O(|S|)\).
• Space complexity: \(O(\sum |S| + \sum |T|)\)
  • All input data is stored in memory.

※ In practice, since the constraints are lenient, the optimized subsequence checking is more than fast enough.

Implementation Notes

• Using sys.stdin.read to read all input at once and split it reduces input processing time.

• Subsequence checking using all(c in it for c in t) with iterators is both concise and fast.

• For each query, since a bookshelf counts as long as “at least one book matches,” using any() makes the code clean and efficient.

  Source Code

def is_subsequence(s, t):
    it = iter(s)
    return all(c in it for c in t)

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    
    shelves = []
    for _ in range(N):
        K = int(data[idx])
        idx += 1
        titles = data[idx:idx+K]
        idx += K
        shelves.append(titles)
    
    Q = int(data[idx])
    idx += 1
    queries = data[idx:idx+Q]
    
    results = []
    for T in queries:
        count = 0
        for shelf in shelves:
            if any(is_subsequence(title, T) for title in shelf):
                count += 1
        results.append(count)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.