問題文の指示通り、各本に対して検索を行います。

まずは「文字列 \(X\) が文字列 \(Y\) を部分列として持つか」という問題に答えることを考えます。この問題は \(X\) の先頭から貪欲に \(Y\) の文字をマッチさせる、次のような方法で \(O(|X|)\) 時間で解くことができます。

• \(X\) の先頭の文字を指すカーソルを用意する
  • \(Y\) の先頭の文字から順に、 \(X\) のカーソルを進めながら文字を探す

よって、 1回の検索クエリには \(O(\sum|S_{i,j}|)\) 時間で答えることができ、全体で \(O(Q\sum|S_{i,j}|+\sum|T_i|)\) 時間でこの問題を解くことができます。

「文字列 \(X\) は文字列 \(Y\) を部分列として持つか？」の判定は関数を作ると良いでしょう。ただし、実装によっては、関数呼び出しの際に引数となる文字列のコピーが行われ、計算量が \(O(Q\sum|S_{i,j}|+(\sum|T_i|)(\sum K_i))\) に悪化するため注意してください。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<vector<string>>s(n);
  for(int i=0; i<n; i++){
    int k;
    cin >> k;
    vector<string>si(k);
    for(int j=0; j<k; j++) cin >> si[j];
    s[i] = si;
  }

  auto f=[&](string s, string& t){
    int pos = 0;
    for(int i=0; i<t.size(); i++){
      while(pos < s.size() && s[pos] != t[i]){
        pos++;
      }
      if(pos == s.size()){
        return false;
      }
      pos++;
    }
    return true;
  };

  int q;
  cin >> q;
  for(int qq=0; qq<q; qq++){
    string t;
    cin >> t;
    int ans = 0;
    for(auto si: s){
      bool hit = false;
      for(string sij: si){
        hit |= f(sij, t);
      }
      if(hit){
        ans++;
      }
    }
    cout << ans << endl;
  }
}

実装例 (Python)

N = int(input())
S = []
for _ in range(N):
  _, *SS = input().split()
  S.append(SS)

def f(S, T):
  # S は T を部分列に持つか？
  pos = 0
  for t in T:
    while pos < len(S) and S[pos] != t:
      pos += 1
    if pos == len(S):
      return False
    pos += 1
  return True

Q = int(input())
for _ in range(Q):
  T = input()
  ans = 0
  for SS in S:
    if any(f(s, T) for s in SS):
      ans += 1
  print(ans)