Codeforces 633C Spy Syndrome 2（DP+Trie树）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 #define MAXN 1111111
 8 int tn,ch[MAXN][26],flag[MAXN];
 9 void insert(const char *s,int k){
10     int x=0,y;
11     for(int i=0; s[i]; ++i){
12         if(s[i]>=‘A‘ && s[i]<=‘Z‘) y=s[i]-‘A‘;
13         else y=s[i]-‘a‘;
14         if(ch[x][y]==0) ch[x][y]=++tn;
15         x=ch[x][y];
16     }
17     flag[x]=k;
18 }
19 
20 int d[11111];
21 char str[11111];
22 string word[110000];
23 void output(int n){
24     if(n<0) return;
25     output(n-word[d[n]].length());
26     cout<<word[d[n]]<<‘ ‘;
27 }
28 int main(){
29     int n,m;
30     scanf("%d%s%d",&n,str,&m);
31     for(int i=1; i<=m; ++i){
32         cin>>word[i];
33         insert(word[i].c_str(),i);
34     }
35     for(int i=0; i<n; ++i){
36         int x=0;
37         for(int j=i; j>=0; --j){
38             int y=str[j]-‘a‘;
39             if(ch[x][y]==0) break;
40             x=ch[x][y];
41             if(flag[x] && (i-(i-j+1)<0 || d[i-(i-j+1)])){
42                 d[i]=flag[x];
43                 break;
44             }
45         }
46     }
47     output(n-1);
48     return 0;
49 }