题目地址：http://poj.org/problem?id=1625
一样是拿母串在trie上搜索，且不经过危险节点
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
typedef long long LL;
struct BigInteger{int num[300]; int len;BigInteger(){ memset(num,0,sizeof(num)); len=0; } void output(){ for(int i=len-1;i>=0;i--) cout<<num[i]; cout<<endl; }
};
BigInteger operator + (BigInteger s1,BigInteger s2)
{ if(s1.len<s2.len) { BigInteger temp=s1; s1=s2; s2=temp; } int k=0; for(int i=0,j=0;i<s1.len;i++,j++) { k+=s1.num[i]+s2.num[j]; s1.num[i]=k%10; k/=10; } while(k) { s1.num[s1.len++]=k%10; k/=10; } return s1;
}
const int letter=55;
const int INF=0x3f3f3f3f;
struct Node{Node *pChilds[letter],*pPrev;bool bBadNode;
}tree[100+5];
char patten[50+5];
char str[50+5];
map<char,int> idx;
BigInteger d[50+5][100+5];
int nNode,N,M,P;
//d[i][j]要长度为i到达节点j，也即是tree[j] 字符串个数
void Insert(Node* root,char* s)
{for(int i=0;s[i];i++){if(root->pChilds[idx[s[i]]]==NULL)root->pChilds[idx[s[i]]]=tree+nNode++;root=root->pChilds[idx[s[i]]];}root->bBadNode=true;
}
void BuildDfa()
{for(int i=0;i<N;i++)tree[0].pChilds[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<N;i++){Node* p=root->pChilds[i];if(p==NULL) continue;Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChilds[i]!=NULL){p->pPrev=pPrev->pChilds[i];if(p->pPrev->bBadNode) p->bBadNode=true;break;}else pPrev=pPrev->pPrev;}Q.push(p);}}
}
int main()
{scanf("%d%d%d",&N,&M,&P);scanf("%s",str);for(int i=0;str[i];i++) idx[str[i]]=i;nNode=2;for(int i=0;i<P;i++){scanf("%s",patten);Insert(tree+1,patten);}BuildDfa();d[0][1].num[d[0][1].len++]=1;for(int i=0;i<M;i++)for(int j=1;j<nNode;j++){if(tree[j].bBadNode) continue;for(int k=0;k<N;k++){Node* pPrev=tree+j;while(pPrev){if(pPrev->pChilds[k]!=NULL){if(pPrev->pChilds[k]->bBadNode) break;int son=pPrev->pChilds[k]-tree;d[i+1][son]=d[i+1][son]+d[i][j];break;} pPrev=pPrev->pPrev;} } }BigInteger result[105];int k=0;result[0].num[result[0].len++]=0;for(int i=1;i<nNode;i++)k++,result[k]=d[M][i]+result[k-1];result[k].output();return 0;
}