【问题描述】
给出一个由S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接（单词可以重复使用），有多少种方法？
比如4个单词：{“a”,”b”,”cd”,”ab”}，则”abcd”有两种分解方法：”a”+”b”+”cd” 或 “ab”+”cd”。
【输入格式】
第一行为长字符串（仅由小写字母组成）。 第二行一个整数n，表示字典包含的单词数。以下n行，每行为一个单词。
【输出格式】
输出长字符串的分解方案数除以 20071027 的余数。
【输入样例】
abcd 4 a b cd ab
【输出样例】
2
【样例解释】
时间限制：1秒 内存限制：64M
【数据范围】
n<=40000 长字符串长度不超过1 000 000，每个单词长度不超过100。
【来源】
大白书209页，LA3942
建立一棵trie树然后在原字符串上进行简单的动态规划就可以了。 d(i)完成了前i-1个字母有多少中情况。 以每一个字母为起点，在trie树上找有没有对应的单词，比如说i到j个字母为一个单词，d(j)=d(j)+d(i)，这样就可以得出答案了。
详细代码如下：
#include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=2000005; const int mod=20071027; int ch[maxn][26]={0},cnt=0,n,root=0,m; bool vis[maxn]={0}; char s[1000005],c[105]; int d[1000005]; void in()//建trie树 { int p=root,i=0,k; while(1) { if(c[i]==0) { vis[p]=1; return; } int k=c[i]-'a'; if(!ch[p][k]) ch[p][k]=++cnt; p=ch[p][k]; i++; } } void work(int i) { int p=root,k,j=i; while(i<=m) { if(vis[p])//找到了对应的单词 { d[i]=(d[i]+d[j])%mod; } int k=s[i]-'a'; p=ch[p][k]; if(!p) break;//一定要记得break，没有找的就跳出来 i++; } } int main() { freopen("in.txt","r",stdin); freopen("ou.txt","w",stdout); scanf("%s",s); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",c); in(); } d[0]=1; m=strlen(s); for(int i=0;i<m;i++)//动规 { work(i); } cout<<d[m]; return 0; }