1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <string.h>  5 #include <string>  6 #include <queue>  7 #include <map>  8 using namespace std;  9 const int N=52*2; 10 char str[52],s1[52]; 11 map<char,int> map1; 12 int ch[N][52],fail[N],val[N],sz,root,n; 13  14 struct BigInt{ 15     int v[100],len; 16     BigInt(int t=0){ 17         memset(v,0,sizeof(v)); 18         for(len=0;t>0;t/=10){ 19             v[len++]=t%10; 20         } 21     } 22     BigInt operator + (const BigInt &a){ 23         BigInt ans; 24         int i,c=0; 25         for(i=0;i<a.len||i<len||c>0;i++){ 26             if(i<len)c+=v[i]; 27             if(i<a.len)c+=a.v[i]; 28             ans.v[i]=c%10; 29             c/=10; 30         } 31         ans.len=i; 32         return ans; 33     } 34     void print(){ 35         if(len==0)printf("0\n"); 36         else { 37             for(int i=len-1;i>=0;i--){ 38                 printf("%d",v[i]); 39             } 40         printf("\n"); 41         } 42     } 43 }dp[52][N]; 44  45  46 int newnode(){ 47     memset(ch[sz],-1,sizeof(ch[sz])); 48     val[sz]=0; 49     return sz++; 50 } 51 void init(){ 52     sz=0; 53     root=newnode(); 54 } 55 void  insert(char* str1){ 56     int len=strlen(str1); 57     int now=root; 58     for(int i=0;i<len;i++){ 59         int &tem=ch[now][map1[str1[i]]]; 60         if(tem==-1){ 61             tem=newnode(); 62         } 63         now=tem; 64     } 65     val[now]=1; 66 } 67  68  69 void getfail(){ 70     queue<int> q; 71     fail[root]=root; 72     for(int i=0;i<n;i++){ 73         int &u=ch[root][i]; 74         if(u==-1)u=root; 75         else { 76             fail[u]=root; 77             q.push(u); 78         } 79     } 80     while(!q.empty()){ 81         int now=q.front(); 82         q.pop(); 83         for(int i=0;i<n;i++){ 84             if(ch[now][i]==-1){ 85                 ch[now][i] = ch[fail[now]][i]; 86             } 87             else{ 88                 fail[ch[now][i]]=ch[fail[now]][i]; 89                 val[ch[now][i]]+=val[fail[ch[now][i]]]; 90                 q.push(ch[now][i]); 91             } 92         } 93     } 94 } 95 void getsum(int l){ 96     for(int i=0;i<52;i++){ 97         for(int j=0;j<sz;j++)dp[i][j]=BigInt(); 98     } 99     dp[0][root] = BigInt(1);100     for(int i=0;i<l;i++){101         for(int j=0;j<sz;j++){102             if(val[j])continue;103             for(int k = 0;k <n;k++){104                 if(val[ch[j][k]])continue;105                 dp[i+1][ch[j][k]] = dp[i+1][ch[j][k]]+dp[i][j];106             }107         }108     }109     BigInt ans;110     for(int i=0;i<sz;i++)111         ans = ans + dp[l][i];112     ans.print();113 }114 int main(){115     int m,p;116     scanf("%d%d%d",&n,&m,&p);117     getchar();118     scanf("%s",str);119     for(int i=0;i<n;i++){120         map1[str[i]]=i;121     }122     init();123     for(int i=0;i<p;i++){124         scanf("%s",s1);125         insert(s1);126     }127     getfail();128     getsum(m);129     return 0;130 131 }