题目链接：题目传送门 题目大意： 现在军方截获了一段被加密的信息，敌人很狡猾，这段信息中有很多无用的字符。 现从另一情报处得到了n个可能是真要正表达的信息，为了确定这段信息，首先需要确定他是否是加密信息的一部分并且是原本的顺序。 现在你作为一名专业破译员，请你来解决这个问题
例如：在abcabd中，c，abcabd，abc，ad都属于，而aaa，cba，e不属于。 Input 第一行一个字符串S(|S| <= 1e5)，表示加密的信息。 第二行一个整数n(n <= 1e5)，表示可能信息的数量 接下来n行， 每行一个字符串C(|C| <= 1000)，表示可能的信息。 Output 对于每个信息，请输出他是否为加密信息的一部分 若是则输出“YES”,否则输出“NO”。 Sample Input
abcabd 7 c abcabd abc ad aaa cba eSample Output
YES YES YES YES NO NO NO思路： trie(字典树)是可以用来查找是否是子串，不过需要处理，因为这个可以是不连续的 代码：
#include<iostream> #include<set> #include<vector> #include<queue> #include<string.h> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<map> using namespace std; typedef long long int ll; 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 i=0;i<26;i++)trie[len+1][i]=-1;//初始化，因为len+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++) { scanf("%s",s); int cur=0; 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; } /**/