【题意】给出一个有S个不同单词组成的字典和一个字符串。把这个字符串分解成若干个单词的连接,有多少种方法?
【解题方法】令dp[i]表示以字符i结束的字符串的分解方案数,即dp[i+j] = sum(dp[i]) (j为一个单词的长度),初始化dp[0] = 1;把所有单词组成Trie,然后试着在Trie中查找单词即可。
<address>【AC代码】</address>
//File Name: Trie Tree.
//Created Author: zxy
//2016/8/1 14:20
//All Rights Reserved.
/************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=300010;
const int maxm=4000010;
const int mod=20071027;
char str[maxn];
int dp[maxn];
struct node{
int ch[maxm][26];//ch[0]代表根节点
int flag[maxm];//标记某个单词是否出现
int sz;
int idx(char c){return c-'a';}
void init(){sz=1;memset(ch[0],0,sizeof(ch[0]));}//只有一个根节点
void Insert(char *s,int v){
int u=0,le=strlen(s);
for(int i=0; i<le; i++){
int now=idx(s[i]);
if(!ch[u][now]){
memset(ch[sz],0,sizeof(ch[sz]));
flag[sz]=0;
ch[u][now]=sz++;
}
u=ch[u][now];
}
flag[u]=v;//插入完成打标记
}
int Find(char *s){
int le=strlen(s);
int u=0;
for(int i=0; i<le; i++){
int now=idx(s[i]);
if(!ch[u][now]) return 0;
u=ch[u][now];
}
return flag[u];
}
}Trie;
int main()
{
char op[110];
int n,cas=1;
// scanf("%d",&T);
while(~scanf("%s",str+1))
{
Trie.init();
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%s",op);
Trie.Insert(op,1);
}
dp[0]=1;
int le=strlen(str+1);
str[0]='#';
for(int i=0; str[i]; i++){
int u=0;
for(int j=1; j<=le; j++){
int now=Trie.idx(str[i+j]);
u=Trie.ch[u][now];
if(!u) break;
else if(Trie.flag[u]==1){
dp[i+j]=(dp[i+j]+dp[i])%mod;
}
}
}
printf("Case %d: %d\n",cas++,dp[le]);
}
}