题解 | #月月查华华的手机#

记录每个字母出现的位置，查找的时候用二分优化，时间复杂度nlogn

#include<iostream>
#include<vector>
using namespace std;
string str;
char t[1000005];
int n;
vector<int> space[150];

int binary_search(const vector<int> &arr, int k) {
	int l = 0, r = arr.size() - 1, middle;
	if(r == -1) return -1;
	while(l < r) {
		middle = (l + r) / 2;
		if(arr[middle] < k) l = middle + 1;
		else r = middle;
	}
	if(arr[l] < k) return -1;
	return arr[l];
}

int main() {
	cin >> str;
	for(int i = 0; str[i]; i++) {
		space[str[i] - 'A'].push_back(i);
	}
	int n;
	cin >> n;
	while(n--) {
		scanf("%s", t);
		int s = 0;
		int flag = 1;
		for(int i = 0; t[i]; i++) {
			s = binary_search(space[t[i] - 'A'], s);
			if(s == -1) {
				flag = 0;
				break;
			}
			s += 1;
		}
		if(flag) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}