UVA-1401-dp+Trie

给出一个文本串和若干个单词，问由这些单词组成这个文本的不同方案个数

例 abc=a+b+c=ab+c=a+bc=abc 为他的所有可能的组合

方程不难推出一个f[i]=SUM{f[j+1] | j>=i&&s[i,,j]是一个单词 } //其中f[i]表示s[i...sz]的方案个数，如果依次枚举判断这个前缀是不是一个单词的话复杂度达到O(sz^2)太大了，可以建一颗字典树每次从根出发沿着后面的单词走，遇到have为1表示单词存在累加答案否则跳过，走不下去时退出，由于深度最大100，复杂度就是O(100*sz);

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 const int MOD=20071027;
 5 char s[300010];
 6 int ch[200010][26];
 7 bool have[300010];
 8 int f[300010];
 9 int size=0;
10 void insert(char *S)
11 {
12     int n=strlen(S),u=0;
13     for(int i=0;i<n;++i){
14         int c=S[i]-'a';
15         if(!ch[u][c]) ch[u][c]=size++;
16         u=ch[u][c];
17     }
18     have[u]=1;
19 }
20 int main()
21 {
22     char str[110];
23     int cas=0;
24     while(cin>>s+1){
25         int ans=0;
26         size=1;
27         memset(ch,0,sizeof(ch));
28         memset(have,0,sizeof(have));
29         int sz=strlen(s+1);
30         int n,i;
31         cin>>n;
32         for(i=1;i<=n;++i)
33         {
34             scanf("%s",str);
35             insert(str);
36         }
37         f[sz+1]=1;
38         for(i=sz;i>=1;--i)
39         {
40             f[i]=0;
41             int j=i;
42             int u=0;
43             while(j<=sz&&ch[u][s[j]-'a']){
44                 u=ch[u][s[j]-'a'];
45                 if(have[u]) f[i]=(f[i]+f[j+1])%MOD;
46                 j++;
47             }
48         }
49          //if(cas>=1)puts("");
50         printf("Case %d: ",++cas);
51         cout<<f[1]<<endl;
52     }
53     return 0;
54 }