10 2 2 hello world 4 1 1 icpc 10 0 0 0 0 0
2 1 14195065
dp[i][j][k]表示长度为i的串在状态j下各串出现情况。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-3 13:21:05
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int dp[30][110][1<<10],num[1<<10];
const int mod=20090717;
struct Trie{
int next[110][26],fail[110],end[110];
int root,L;
int newnode(){
for(int i=0;i<26;i++)
next[L][i]=-1;
end[L++]=0;
return L-1;
}
void init(){
L=0;
root=newnode();
}
void insert(char *str,int id){
int len=strlen(str);
int now=root;
for(int i=0;i<len;i++){
int p=str[i]-‘a‘;
if(next[now][p]==-1)
next[now][p]=newnode();
now=next[now][p];
}
end[now]|=(1<<id);
}
void build(){
queue<int> q;
fail[root]=root;
for(int i=0;i<26;i++)
if(next[root][i]==-1)
next[root][i]=root;
else {
fail[next[root][i]]=root;
q.push(next[root][i]);
}
while(!q.empty()){
int now=q.front();
q.pop();
end[now]|=end[fail[now]];
for(int i=0;i<26;i++)
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else {
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
int solve(int n,int m,int k){
for(int i=0;i<n;i++)
for(int j=0;j<L;j++)
for(int p=0;p<(1<<m);p++)
if(dp[i][j][p])
for(int q=0;q<26;q++){
int newi=i+1;
int newj=next[j][q];
int newp=p|end[newj];
dp[newi][newj][newp]+=dp[i][j][p];
dp[newi][newj][newp]%=mod;
}
int ans=0;
for(int i=0;i<(1<<m);i++){
if(num[i]<k)continue;
for(int j=0;j<L;j++){
ans=(ans+dp[n][j][i])%mod;
}
}
return ans;
}
}ac;
char str[1000];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n;
for(i=0;i<1024;i++)
for(j=0;j<10;j++)
if(i&(1<<j))
num[i]++;
while(~scanf("%d%d%d",&n,&m,&k)){
if(n==0&&m==0&&k==0)break;
ac.init();
for(i=0;i<m;i++){
scanf("%s",str);
ac.insert(str,i);
}
ac.build();
for(i=0;i<=n;i++)
for(j=0;j<ac.L;j++)
for(int p=0;p<(1<<m);p++)
dp[i][j][p]=0;
dp[0][0][0]=1;
printf("%d\n",ac.solve(n,m,k));
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18909205