题意：n个字符组成长度为m的串，有一系列模式串pi，求不包含这些模式串的串有多少。

分析：对这些模式串构建AC自动机。

AC自动机其实就是trie树+失败指针，原理和KMP算法差不多。

失败指针的建立可以采用BFS，对于每个节点，我们可以这样处理：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root

最开始，我们把root加入队列(root的失败指针显然指向自己)，这以后我们每处理一个点，就把它的所有儿子加入队列，直到搞完。

本题中，设dp[i][j]为串的长度为i时候，到达状态j 的数量，

dp[i+1][id] = dp[i][j] + dp[i+1][id]； j是id的父节点。 此时要记得去掉复合模式串的结点。

最后就是要用高精度加法。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
 
using namespace std;

const int MAXC = 50;
const int MAXN = 500;
 
template<int LIM,int MAX> class hp{
    public:
        //vars
        int sect[MAX];
        int scnt;
        //constructors
        hp(){
            scnt=1;
            sect[0]=0;
        }
        //functions
        void copy(int A){
            scnt=0;
            while (A){
                sect[scnt++]=A % LIM;
                A /=LIM;
            }
        }
        void copy(const hp<LIM,MAX> &A)
        {
            for (int i=0;i<A.scnt;i++)
                sect[i]=A.sect[i];
            scnt=A.scnt;
        }
        void print(){
            int i,k;
            printf("%d",sect[scnt-1]);
            for (i=scnt-2;i>=0;i--){
                k=LIM/10;
                while(sect[i]<k){
                    printf("0");
                    k/=10;
                }
                if (sect[i])
                    printf("%d",sect[i]);
            }
        }
        void read(int LIE){
            char A[LIM*MAX];
            int len,i,j,k,b=0;
            scanf("%s",A);
            len=strlen(A);
            k=len % LIE;
            j=scnt=len / LIE;
            if (k){
                scnt++;
                j=scnt-1;
                sect[j]=0;
                for (i=0;i<k;i++){
                    sect[j]*=10;
                    sect[j]+=A[b++]-'0';
                }
            }
            for (j--;j>=0;j--){
                sect[j]=0;
                for (i=0;i<LIE;i++){
                    sect[j]*=10;
                    sect[j]+=A[b++]-'0';
                }
            }
        }
        void plus(hp<LIM,MAX> &A,int offset=0){
            int sc=scnt > A.scnt + offset  ? scnt : A.scnt + offset;
            int i,j,up=0;
            for (i=0;i<sc;i++){
                j=i - offset;
                if (j<0) continue;
                if (i>=scnt) sect[i]=0;
                if (j>=A.scnt) A.sect[j]=0;
                sect[i]+=A.sect[j] + up;
                up=sect[i] / LIM;
                sect[i]%=LIM;
            }
            scnt=sc;
            if (up) sect[scnt++]=up;
        }
        //operators
        
        void operator =(hp<LIM,MAX> A){
            copy(A);
        }
        void operator =(int A){
            copy(A);
        }
        void operator +=(hp<LIM,MAX> &A){
            plus(A);
        }
        hp<LIM,MAX> operator +(hp<LIM,MAX> &A){
            hp<LIM,MAX> C(*this);
            C.plus(A);
            return C;
        }
};
 
typedef hp<10000,50> hpnum;

struct node {
       int  f,id;
       node *fail;
       node *next[MAXC]; 
};

node list[MAXN];
int nodeCnt ,idx[500] ;
node *root;
node *que[MAXN];

inline node *newnode() {
       node *ans = &list[++nodeCnt];
       ans->f = 0;
       ans->id = nodeCnt;
       ans->fail = NULL;
       for(int i = 0 ; i < MAXC;i++ )
               ans->next[i] = NULL;
       return ans;
}
void insert(char *s) {
       node *p = root;
       while( *s ){
              int id = idx[ *s + 100 ];
              if( p->next[id] == NULL ) p->next[id] = newnode();
              p = p->next[id];
              s++;
       }
       p->f = 1;
}
void ac_automation() {
       int head = 0 ,tail = 1;    
       root->fail = NULL;
       que[head] = root;
       node *p ;
   
       while( head < tail ) {
           p = que[head++];
           for( int i = 0 ; i < MAXC ; i++ ) {
                if( p->next[i] != NULL) {
                    if( p == root ) p->next[i]->fail = root;
                    else {
                         node *tmp = p->fail;
                         while( tmp != NULL ){
                              if( tmp->next[i] != NULL ) {
                                     p->next[i]->fail = tmp->next[i];
                                     if( tmp->next[i]->f == 1) p->next[i]->f = 1; 
                                     break;
                              }
                              tmp = tmp->fail; 
                         }   
                         if( tmp == NULL ) p->next[i]->fail = root;
                    } 
                    que[tail++] = p->next[i];
                }
           }
       }
}

hpnum dp[MAXC+5][505];
int  n, m;

void solve() {
     int i , j, k; 

     dp[0][1]=1;
     for( i = 0 ; i < m;i++ )
       for( j = 1 ; j<=nodeCnt; j++ )
         for( k = 0 ; k < n ; k++ ) {
              node *tmp = list[j].next[k];
              if( tmp != NULL) {
                  int  id = list[j].next[k]->id;
                  if( list[j].next[k]->f == 0)
                      dp[i+1][id] = dp[i][j] + dp[i+1][id] ;
              }
              else {
                   node *p = list[j].fail;
                   while( p ) {
                          if( p->next[k] != NULL ) break;
                          p = p->fail;
                   }
                   if( p == NULL ) p = root;
                   else  p = p->next[k];
                   if( p->f == 0 ) 
                       dp[i+1][p->id] = dp[i][j] + dp[i+1][p->id];
              }
         }
     
     hpnum  ans ;
     for( i = 1 ; i <= nodeCnt; i++ ) 
       ans += dp[m][i] ;
     ans.print();
     cout<<endl;
}

int main() {
    int i,p;
    while( scanf("%d%d%d",&n,&m,&p) != EOF) {
           nodeCnt = 0;
           root = newnode();
           char   s[100];
           scanf("%s",s);
           for( i = 0 ; i < strlen(s) ;i++)
                idx[ s[i] + 100 ] = i;
           for( i = 0 ;i < p ;i++ ) {
                scanf("%s",s);
                insert(s);
           }
           ac_automation();
           solve();
    }
    return 0;
}