[LA 3942]Remember the Word
转载请注明出处:http://danihao123.is-programmer.com/
Trie第一题……
首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。
这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~
代码:
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn=300005; const int maxW=4005,maxL=105; const int MOD=20071027; #define REP(i,n) for(i=0;i<(n);i++) #define REP_B(i,n) for(i=1;i<=(n);i++) #define DREP(i,n) for(i=(n)-1;i>=0;i--) #define CL_ARR(x,v) memset(x,v,sizeof(x)) int n; vector<int> AnsList; namespace Trie{ const int maxnode=400005; const int sigma_siz=26; int Tree[maxnode][sigma_siz]; int val[maxnode]; int siz; inline int idx(char c){ return c-'a'; } inline void InitTrie(){ siz=0; val[0]=0; CL_ARR(Tree[0],0); } void Insert(char *s,int v){ register int u=0,n=strlen(s); register int i,c; REP(i,n){ c=idx(s[i]); if(!Tree[u][c]){ siz++; Tree[u][c]=siz; val[siz]=0; CL_ARR(Tree[siz],0); } u=Tree[u][c]; } val[u]=v; } void Query(char *s,int len){ register int i,c,u=0; AnsList.clear(); REP(i,len){ if(!s[i]) break; c=idx(s[i]); if(!Tree[u][c]) break; u=Tree[u][c]; if(val[u]) AnsList.push_back(val[u]); } } }; char Text[maxn]; int len[maxW]; char buf[maxL]; int d[maxn]; int main(){ register int i,j,Case=0; int m; while(scanf("%s%d",Text,&m)==2){ Case++; n=strlen(Text); Trie::InitTrie(); REP_B(i,m){ scanf("%s",buf); len[i]=strlen(buf); Trie::Insert(buf,i); } d[n]=1; DREP(i,n){ d[i]=0; Trie::Query(Text+i,n-i); REP(j,AnsList.size()){ d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD; } } printf("Case %d: %d\n",Case,d[0]); } return 0; }