実装方針

各 \(S_j\) の \(i\) 文字目について，以下を高速に判定することを考えます．

• 長さ \(A_i\) 文字で，\(B_i\) 文字目が \(S_j[i]\) と一致するような文字列が \(S_1, \cdots, S_M\) のなかに存在するか？

これを愚直な実装から高速化することは困難に見えます．そこで，前もって必要な値を求めておくことを考えます．

\(\mathrm{memo}[len][place][c]\) を，「長さ \(len\) 文字で，\(place\) 文字目が \(c\) と一致するような文字列が \(S_1, \cdots, S_M\) のなかに存在する」かどうかを表すべき値とします．これらを False で初期化し，以下の前処理を行います．

• 各 \(S_j\) の \(i\) 文字目について，その文字が \(c\) のとき，\(\mathrm{memo}[|S_j|][i][c]\) を True にする．

この前処理は \(O(N^2_{max} \sigma + N_{max}M)\) 時間で動きます(\(N_{max} := \max(|S_1|, \cdots, |S_M|)\)．また，\(\sigma\) は文字の種類数)． この前処理が終わった時点で，\(\mathrm{memo}\) の各値は正しい値をもちます．

判定は各位置について \(O(1)\) 時間で行えるようになったので，全体で \(O(N^2_{max} \sigma + N_{max}M)\) 時間で動き，十分高速です．

実装例 (C++)

C++ での実装例を以下に示します．

なお，この実装例は英小文字 (a-z) の文字コードが連続であることを前提にしています． そのため，AtCoder のジャッジサーバをはじめとする主流の環境では意図通りに動作しますが，必ずしも手元の環境で意図通りに動くとは限りません．

#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
#include <string>
using std::string;

typedef long long int ll;

const int MAX_N = 10;
const int SIGMA = 26;

int n, m;
vector<int> a, b;
vector<string> s;

void solve () {
	// has[i][j][k] == 1 iff there exists s such that |s| == i, s[j] == ('a' + k)
	int has[MAX_N + 1][MAX_N][SIGMA];
	// init with 0
	for (int i = 0; i <= MAX_N; i++) {
		for (int j = 0; j < MAX_N; j++) {
			for (int k = 0; k < SIGMA; k++) {
				has[i][j][k] = 0;
			}
		}
	}
	// set 1
	for (int i = 0; i < m; i++) {
		int sz = s[i].size();
		for (int j = 0; j < sz; j++) {
			has[sz][j][s[i][j] - 'a'] = 1;
		}
	}

	vector<int> isyes(m, 0);
	// answer for each s
	for (int i = 0; i < m; i++) {
		int sz = s[i].size();
		if (sz != n) continue;

		bool isok = true;
		for (int j = 0; j < n; j++) {
			if (has[a[j]][b[j] - 1][s[i][j] - 'a'] == 0) isok = false;
		}
		if (isok) {
			isyes[i] = 1;
		}
	}

	// output
	for (int i = 0; i < m; i++) {
		cout << (isyes[i] ? "Yes" : "No") << "\n";
	}
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n;
	a.resize(n);
	b.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}

	cin >> m;
	s.resize(m);
	for (ll i = 0; i < m; i++) {
		cin >> s[i];
	}


	solve();

	return 0;
}