[LA 3942]Remember the Word
转载请注明出处：http://danihao123.is-programmer.com/
Trie第一题……
首先，容我吐槽一下UVa这个OJ，速度特别感人（同学们可以实践一下）。
这个题最容易想到的是的DP——对于
，枚举其前缀查是否为单词，然后转移。但是啊……对于
这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个，在前缀树中查找之，就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100，所以查找会很快辣~
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #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;} |
评论 (0)
