题意:
给定一个长度不超过30000的字符串str,然后给定n(n<=4000)个长度不超过100的字符串ai,问用ai组合成str有多少种方案数,最终结果mod20071027。
题解:
dp公式很好推,dp[i]表示从i开始到str末尾有多少种组合方案,那么dp公式为dp[i]=∑dp[k+1](k>=i,且区间[i,k]所构成的字符串在ai种存在)。
如果直接暴力,时间上会TLE,所以我们需要用字典树保存ai,那么每次查找[j,k]不超过100次操作,时间复杂度就可以接受了。
字典树:
向字典那样讲字符串保存在树当中,其中ch[i][j]表示在i状态下,输入字符j时,下个状态的位置是多少(类似与邻接表);val[i]表示i状态的时候是否是一个字符串的终点(也可以记录在这个位置终结的字符串的个数)。
其中ch[i][j]中j范围为字符集范围,例如小写字母是26个,0<=j<26;i就比价大,最坏的情况下为str的长度*ai的最大长度,这样很可能超出内存,不过这种情况基本不会出现,如果内存不够可以开更小的数组或者改用指针形式的字典树。
代码:
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <vector> using namespace std; #define LL long long const int maxn=4001*101; const int maxm=3e5+10; const int mod=20071027; struct Trie{ int ch[maxn][26]; int val[maxn]; int sz; Trie(){sz=1;memset(ch[0],0,sizeof(ch[0]));} int idx(char c){return c-'a';} void insert(char *s,int v) { int i,u=0,n=strlen(s); for(i=0;i<n;i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; } }e; char str[maxm]; char a[101]; LL dp[maxm]; int main() { int tt=0; while(scanf("%s",str)!=EOF) { int i,j,k,n,m,u; scanf("%d",&n); memset(e.ch[0],0,sizeof(e.ch[0])); e.sz=1; for(i=0;i<n;i++) { scanf("%s",a); e.insert(a,1); } m=strlen(str); memset(dp,0,sizeof(dp)); dp[m]=1; for(i=m-1;i>=0;i--) { u=0; for(j=i;j<m;j++) { int c=e.idx(str[j]); if(!e.ch[u][c])break; u=e.ch[u][c]; if(e.val[u])dp[i]+=dp[j+1]; } dp[i]%=mod; } printf("Case %d: %lld\n",++tt,dp[0]); } return 0; }