CF #Manthan, Codefest 16 C. Spy Syndrome 2 Trie

题目链接：http://codeforces.com/problemset/problem/633/C

大意就是给个字典和一个字符串，求一个用字典中的单词恰好构成字符串的匹配。

比赛的时候是用AC自动机写的，就是对于trie中每一个节点，判断是否为终结点，以及当前字符所在位置p减去trie中这个节点的深度也即某一单词的长度l，判断dp[p-l]是否可以被构成，可以的话直接break并且标记当前dp值。

赛后想了想，其实直接一个trie就行了，每个单词才1000的长度，又想起来我去年给人讲过类似的问题，当时我自己非常清楚这种单词构成用个简单的tire来搞就行。怎么比赛的时候就写了个AC自动机了呢。

 #include <iostream>
 #include <vector>
 #include <algorithm>
 #include <string>
 #include <string.h>
 #include <stdio.h>
 #include <math.h>
 #include <stdlib.h>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set>
 #include <ctime>
 #include <numeric>
 #include <cassert> using namespace std;
 const int N=;
 string dic[N];
 char str[N],pat[N];
 int mark[N];
 const int CHARSET=,BASE='a',MAX_NODE=;
 struct Trie {
     int tot,root,child[MAX_NODE][CHARSET];
     int flag[MAX_NODE];
     Trie(){
         init();
     }
     void init(){
         root=newNode();
     }
     int newNode() {
         ++tot;
         memset(child[tot],,sizeof(child[tot]));
         flag[tot]=;
         return tot;
     }
     void insert(const char *str,int id){
         int *cur=&root;
         for (const char *p=str;*p;++p){
             cur=&child[*cur][*p-BASE];
             if (*cur==)
                 *cur=newNode();
         }
         flag[*cur]=id;
     }
     void query(int x){
         int *cur=&root;
         for (int i=x;i>=;i--){
             char ch=str[i];
             cur=&child[*cur][ch-BASE];
             if ((*cur)==) break;
             if (flag[*cur]&&mark[i-]!=-){
                 mark[x]=flag[*cur];
                 break;
             }
         }
     }
 }trie;
 int main () {
     int n;
     scanf("%d",&n);
     scanf("%s",str+);
     int m;
     scanf("%d",&m);
     for (int i=;i<=m;i++) {
         scanf("%s",pat);
         dic[i]=string(pat);
         int len=dic[i].length();
         for (int j=;j<=len;j++)
             if (pat[j]>='A'&&pat[j]<='Z')
                 pat[j]+='a'-'A';
         trie.insert(pat,i);
     }
     memset(mark,-,sizeof mark);
     mark[]=;
     for (int i=;i<=n;i++){
         trie.query(i);
     }
     vector<int> ret;
     int now=n;
     while (now>) {
         ret.push_back(mark[now]);
         now-=dic[mark[now]].length();
     }
     for (int i=(int)ret.size()-;i>=;i--) {
         printf("%s ",dic[ret[i]].c_str());
     }
     return ;
 }