Approach

For the \(i\)-th character of each \(S_j\), consider determining the following fast:

• Among \(S_1, \cdots, S_M\), is there a string of length \(B_i\), and the \(A_i\)-th string coincides with \(S_j[i]\)?

It seems difficult to optimize a naive algorithm, so we will try to precalculate necessary values.

Let \(\mathrm{memo}[len][place][c]\) be the value representing whether there exists a string of length \(n\) whose \(place\)-th character is \(c\) among \(S_1, \cdots, S_M\). Initialize them with False, and perform the following preprocess:

• For each \(i\)-th character of \(S_j\), if it equals \(c\), set \(\mathrm{memo}[|S_j|][i][c]\) to True.

This preprocess runs in \(O(N^2_{max} \sigma + N_{max}M)\) time (where \(N_{max} := \max(|S_1|, \cdots, |S_M|)\) and \(\sigma\) is the size of alphabet). Once the preprocess is done, all \(\mathrm{memo}\) contain correct values.

This enables \(O(1)\) determination for each position, for a total runtime of \(O(N^2_{max} \sigma + N_{max}M)\), which is fast enough.

Sample code (C++)

The following is sample code in C++.

Note that we assume that lowercase English letters (a-z) have consecutive character codes. Thus, while this code runs in most mainstream environment, it is not guaranteed to work as intended in your environment.

#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;
}