Codeforces 633C Spy Syndrome 2 【Trie树】+【DFS】

题目大意：
给定一个只有小写字母组成的目标串和m个模式串(里面可能有大写字母)，记目标串反过来后的串为S，让你从m个模式串中选出若干个组成S串(不区分大小写)。输出任意一种方案。

解题分析：
将所有单词倒着建好Trie树后(字母忽略大小写)，直接在Trie树上跑DFS，记录下所有符合条件的单词序号，然后输出即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N =1e6+10;
 7 const int M =1e5+10;
 8 int n,m;
 9 char s[M],word[M][1005];
10 int trie[N][27],mark[N],ans[M],cnt,tot;
11 void Insert(char *str,int ord){
12     int now=0,len=strlen(str);
13     for(int i=len-1;i>=0;i--){    //对这些单词进行逆序插入
14         int to;
15         if(str[i]>'Z')to=str[i]-'a';    //忽略单词的大小写
16         else to=str[i]-'A';
17         if(!trie[now][to])
18             trie[now][to]=++tot;
19         now=trie[now][to];
20     }
21     mark[now]=ord;    //记录下该单词的编号
22 }
23 bool dfs(int loc){
24     if(s[loc]=='

Codeforces 633C Spy Syndrome 2 【Trie树】+【DFS】

相关推荐