题目大意：

要求构造一个串，使得这个串是由所给的串相连接构成，连接可以有重叠的部分。

思路分析：

首先用所给的串建立自动机，每个单词节点记录当前节点能够达到的最长后缀。

开始的时候想的是dp[i][j]表示长度为i，走到自动机的j节点的答案。

但是显然既然是可以重复覆盖的，那么每一个节点的dp值都并不是最优的，因为可以从一个地方截断去连接另外一个串。

所以正确姿势就是dp [i] [j] [k] 表示构造到了长度为 i 的串， 现在这个串后面有k 个字符是没有找到有效的节点的，然后在自动机上走到了j。

那么转移的时候，就有两种情况。

isword >= k+1。。。为什么是k+1 因为我们现在是去找的儿子节点，已经加1了。这样的话就是这个节点可以完全覆盖没有匹配到的k个，换句话说就是让后面的k个字符找到了合法节点去匹配。那么就转移到dp [i+1] [j->next] [0]...

否则，如果k+1<=10 那么就让后面这个继续失配，那么久直接转移到 dp [i+1][j->next][k+1]...

最后累加答案。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #define inf 0x3f3f3f3f using namespace std; const int mod = 1000000009; const char tab = 'a'; const int max_next = 4; int rev[256]; struct trie { struct trie *fail; struct trie *next[max_next]; int isword; int index; }; struct AC { trie *que[100005],*root,ac[100005]; int head,tail; int idx; trie *New() { trie *temp=&ac[idx]; for(int i=0;i
         
          next[i]=NULL; temp->fail=NULL; temp->isword=0; temp->index=idx++; return temp; } void init() { idx=0; root=New(); } void Insert(trie *root,char *word,int len){ trie *t=root; for(int i=0;i
          
           next[rev[word[i]]]==NULL) t->next[rev[word[i]]]=New(); t=t->next[rev[word[i]]]; } t->isword=len; } void acbuild(trie *root){ int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head
           
            next[i]){ if(temp==root)temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL){ if(p->next[i]){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL)temp->next[i]->fail=root; } if(temp->next[i]->fail->isword) temp->next[i]->isword=max(temp->next[i]->isword,temp->next[i]->fail->isword); que[tail++]=temp->next[i]; } else if(temp==root)temp->next[i]=root; else temp->next[i]=temp->fail->next[i]; } } } void tra() { for(int i=0;i
            
             index); for(int k=0;k
             
              index); puts(""); } } }sa,sb; string cq[55]; char word[55]; int dp[1005][105][11]; void add(int &a,int b) { a+=b; if(a>=mod)a-=mod; } int solve(int L) { memset(dp,0,sizeof dp); dp[0][0][0]=1; for(int i=0;i
              
               isword>=k+1) add(dp[i+1][sa.ac[j].next[d]->index][0],dp[i][j][k]); else if(k+1<=10) add(dp[i+1][sa.ac[j].next[d]->index][k+1],dp[i][j][k]); } } } } int ans=0; for(int i=0;i
               
                >L>>m) { sa.init(); for(int i=1;i<=m;i++) { cin>>word; sa.Insert(sa.root,word,strlen(word)); } sa.acbuild(sa.root); printf("%d\n",solve(L)); } return 0; }