【计蒜客 - 2019南昌邀请赛网络赛 - M】Subsequence（字典树，dp预处理）

题干：

Give a string SS and NN string T_iTi​ , determine whether T_iTi​ is a subsequence of SS.

If ti is subsequence of SS, print YES,else print NO.

If there is an array \lbrace K_1, K_2, K_3,\cdots, K_m \rbrace{K1​,K2​,K3​,⋯,Km​} so that 1 \le K_1 < K_2 < K_3 < \cdots < K_m \le N1≤K1​<K2​<K3​<⋯<Km​≤N and S_{k_i} = T_iSki​​=Ti​, (1 \le i \le m)(1≤i≤m), then T_iTi​ is a subsequence of SS.

Input

The first line is one string SS,length(SS) \le 100000≤100000

The second line is one positive integer N,N \le 100000N,N≤100000

Then next nn lines,every line is a string T_iTi​, length(T_iTi​) \le 1000≤1000

Output

Print NN lines. If the ii-th T_iTi​ is subsequence of SS, print YES, else print NO.

样例输入复制

abcdefg
3
abc
adg
cba

样例输出复制

YES
YES
NO

题目大意：

   给你一个模板串，再给你n个串，问你这n个串能否由模板串的子序列构成。

解题报告：

出过好几次的套路了。。。刚开始NO没加\n，，，wa一发真可惜、、

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
string ss;
char s[MAX];
int trie[MAX][66];
int main() {
	int n;

	cin>>ss;
	int len = ss.size();
	ss = ' ' + ss;
	for(int j = 0; j<26; j++) trie[len+1][j] = -1;
	for(int i = len; i>=1; i--) {
		for(int j = 0; j<26; j++) {
			if(j == ss[i] - 'a') trie[i][j] = i;
			else trie[i][j] = trie[i+1][j];
		}
	}
	cin>>n;
	for(int i = 1; i<=n; i++) {
		int cur = 0;
		scanf("%s",s);
		int up = strlen(s);
		for(int j = 0; j<up; j++) {
			cur = trie[cur+1][s[j] - 'a'];
			if(cur == -1) {
				break;
			}
		}
		if(cur != -1) printf("YES\n");
		else printf("NO\n");
	}
	return 0 ;
}