Overview

Each bookshelf contains multiple books, and the problem asks us to determine whether a search query is contained as a subsequence of a book’s title, then count the number of bookshelves that have at least one book satisfying the condition.

Analysis

The core of the problem is efficiently determining whether a given query string is a subsequence of each book’s title. Subsequence checking can be done by scanning the title string from the beginning and verifying whether each character of the query appears in order. For each query, we need to check all bookshelves and all books within them, but given the constraints, a brute-force approach is sufficiently fast.

Algorithm

1. Implement a subsequence checking function is_subsequence
   • Determines whether each character of the pattern (query) appears in order within the text (title)
   • Uses an iterator to sequentially scan the text and check whether each character of the pattern is found one after another
2. For each query, perform the following:
   • For each bookshelf, check the books in that bookshelf one by one
   • If at least one book’s title contains the query as a subsequence, count that bookshelf
   • Output the number of bookshelves satisfying the condition

Complexity

• Time complexity: \(O(N \cdot K \cdot L \cdot M)\)
  • \(N\): number of bookshelves (up to 100)
  • \(K\): average number of books per bookshelf
  • \(L\): average title length (up to 1000)
  • \(M\): average query length (up to 1000)
  • Due to the constraint on the total string length (\(10^5\)), this runs in practical time
• Space complexity: \(O(\sum |S_{i,j}| + \sum |T_j|)\)
  • Memory for storing the input data

Implementation Notes

• Using an iterator for subsequence checking allows efficient character matching

• An early break in the inner loop for each bookshelf optimizes performance by moving on to the next bookshelf as soon as one book satisfying the condition is found

• Input data is read line by line and split accordingly for efficient data retrieval

  Source Code

import sys

def is_subsequence(pattern, text):
    it = iter(text)
    return all(c in it for c in pattern)

def main():
    data = sys.stdin.read().splitlines()
    idx = 0
    N = int(data[idx]); idx += 1
    shelves = []
    for _ in range(N):
        parts = data[idx].split(); idx += 1
        k = int(parts[0])
        titles = parts[1:1+k]
        shelves.append(titles)
    
    Q = int(data[idx]); idx += 1
    queries = []
    for _ in range(Q):
        queries.append(data[idx].strip()); idx += 1
    
    for query in queries:
        count = 0
        for shelf in shelves:
            found = False
            for title in shelf:
                if is_subsequence(query, title):
                    found = True
                    break
            if found:
                count += 1
        print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.