题意：容易理解...
分析：在做这道题之前我做了hdu 4057，都是同一种类型的题，因为题中给的模式串的个数最多只能为10个，所以我们就很容易想到用状态压缩来做，但是开始的时候我的代码超时了dp时我们由dp[i][j][k]枚举其后接的字符转移到dp[i+1],在枚举前判断下是否有dp[i][j][k]=0，是的话可以直接continue，而不用再深一层循环.这样优化之后就没超时了。我用了滚动数组实现，其实这题可以不用滚动数组也可以过的，空间上不会卡。
代码实现：
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<queue> #include<cmath> #include<algorithm> using namespace std; struct node{ int next[26]; int fail; int flag; void init() { memset(next,0,sizeof(next)); fail=0; flag=0; } }a[105]; char keyword[15]; int tot,n,m,len; int dp[2][105][1<<10]; void chushihua() { tot=0; a[0].init(); memset(dp,0,sizeof(dp)); } void insert(char *str,int biaohao) { int index,p=0; for(;*str!=' ';str++) { index=*str-'a'; if(a[p].next[index]==0) { a[++tot].init(); a[p].next[index]=tot; } p=a[p].next[index]; } a[p].flag=a[p].flag|(1<<biaohao); } void build_fail() { queue<int>Q; int cur,p,son,i; Q.push(0); while(!Q.empty()) { p=Q.front(); Q.pop(); for(i=0;i<26;i++) { if(a[p].next[i]!=0) { son=a[p].next[i]; cur=a[p].fail; if(p==0) a[son].fail=0; else { // while(cur&&a[cur].next[i]==0) // cur=a[cur].fail; a[son].fail=a[cur].next[i]; } a[son].flag=a[son].flag|a[a[son].fail].flag; Q.push(son); } else a[p].next[i]=a[a[p].fail].next[i]; } } } int panduan(int x) { int i,s=0; for(;x;x=x>>1) if(x&1) s++; if(s>=m) return 1; else return 0; } void solve() { int i,j,k,l,son,sum=0,temp; dp[0][0][0]=1; for(i=1;i<=len;i++) { memset(dp[1&i],0,sizeof(dp[1&i]));//滚动数组 for(j=0;j<=tot;j++) for(l=0;l<(1<<10);l++) { if(dp[1&(i+1)][j][l]==0)//开始这里没加，果断超时了 continue; for(k=0;k<26;k++)//开始的时候这层for循环和上一层for循环调换过来的，没有加那个if判断，导致超时了 { son=a[j].next[k]; temp=l|a[son].flag; dp[1&i][son][temp]+=dp[1&(i+1)][j][l]; if(dp[1&i][son][temp]>=20090717) dp[1&i][son][temp]%=20090717; } } } for(i=0;i<=tot;i++) for(j=0;j<(1<<10);j++) { if(panduan(j)) sum=sum+dp[1&len][i][j]; if(sum>=20090717) sum%=20090717; } printf("%d ",sum); } int main() { int i; while(scanf("%d%d%d",&len,&n,&m)!=EOF&&(len+n+m)!=0) { chushihua(); getchar(); for(i=0;i<n;i++) { scanf("%s",keyword); insert(keyword,i); } build_fail(); solve(); } return 0; }