题意
给定一个字符串和若干个单词,询问能把字符串分解成这些单词的方案数。比如abcd ,有单词a,b,ab,cd:就可以分解成a+b+cd或者ab+cd。
分析
trie树—>DP
代码
(感谢qrc巨神的细心指导,并不是很细心的我竟然也AC了,qrc太巨了!)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MNODE 400000
#define mod 20071027
int trie[MNODE][],cntnode;
bool tag[MNODE];
int dp[];
void init(int x,char *s,int i){
if(i==strlen(s)) {tag[x]=;return;}
char c=s[i];
if(!trie[x][c-'a']) trie[x][c-'a']=++cntnode;
init(trie[x][c-'a'],s,i+);
}
int main(){
char s[];
int S;
int cas=;
while(scanf("%s",s)!=EOF){
memset(trie,,sizeof(trie));
memset(tag,,sizeof(tag));
cntnode=;
scanf("%d",&S);
char ss[];
while(S--) scanf("%s",ss),init(,ss,);
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<strlen(s);i++){
int now=;
for(int j=i;j<strlen(s);j++){
if(trie[now][s[j]-'a']) now=trie[now][s[j]-'a'];
else break;
if(tag[now]) dp[j+]=(dp[j+]+dp[i])%mod;
}
}
printf("Case %d: %d\n",++cas,dp[strlen(s)]);
}
return ;
}