题意:给出一个由S个不同的字符串组成的字典和一个长字符串,问:把这个长字符串分解成若干个字典中出现的字符串,共有几种分法。单词可以重复使用。
思路:将所有字典中的单词插入字典树中,用d[i]表示str[i]到str[n]的所有分解法数。所以有d[i]=sum(i+len(x)),其中x为str[i]为开头的字符串str[i...n],即枚举x,x={str[i]}或{str[i],str[i+1]},........或{str[i]+str[i+1]+str[i+2]+.....+str[n]}.初始化d[n+1]=1。
注意字典树每次执行完一组样例要重新初始化。
#include<cstdio> #include<cstring> #define MOD 20071027 #define maxnode 4010*101 #define MAXLEN 300005 #define sigema_size 26 int ca=0,S,d[MAXLEN]; char str[MAXLEN],tmp[105]; struct Trie { int sz; int ch[maxnode][sigema_size]; int val[maxnode]; void init() {sz=1;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));} int idx(char c) {return c-'a';} void insert(char *s) { int u=0; for(int i=0;s[i];++i) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[c])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=1; } int find(char *s,int a) { int u=0,ans=0; for(int i=a;s[i];++i) { int c=idx(s[i]); if(!ch[u][c]) return ans; u=ch[u][c]; if(val[u]) ans=(ans+d[i+1])%MOD; //如果字典中存在该字符串 } return ans; } }trie; void solve() { int n=strlen(str); d[n]=1;//初始化边界 for(int i=n-1;i>=0;--i) d[i]=trie.find(str,i); printf("Case %d: %d\n",++ca,d[0]); } int main() { freopen("in.txt","r",stdin); while(~scanf("%s",&str)) { trie.init(); scanf("%d",&S); for(int i=0;i<S;++i){scanf("%s",tmp);trie.insert(tmp);} solve(); } return 0; }