题意：给定字符串 \(t_{1...n}\)，你需要构造字符串 \(s\) 使得对于任意 \(i\)，都有至少一对 \([l,r]\) 使得 \(s_{l...r}\) 匹配 \(t_{1...n}\) 中的至少一者，且 \(l \le i \le r\)，并求出替换方案数。
有一个错误的思路，我们不难发现两个匹配区间如果互为包含关系，那么去掉较小区间一定不劣，设 \(f_{i,j}\) 表示前 \(i\) 个字符，以 \(i\) 为结尾的串为 \(j\) 的方案数，转移时枚举上一次结尾的字符串并判断。这样有一个问题，即由于 \(t\) 中可能有重复的字符串，所以该方案会在一些情况下算重，而且不易容斥处理，进而转换思路。
考虑在 AC 自动机上进行 dp，设 \(f_{i,j,k}\) 表示已经填充 \(i\) 个字符，位于 AC 自动机 \(j\) 号节点，长度为 \(k\) 的后缀未被替换的方案数，转移是平凡的。
code:
#include<bits/stdc++.h>
#define N 50005
#define pii pair<int,int>
#define M 1000000009
using namespace std;
int ln,n,tr[N][26],fail[N],f[2][1005][15],num=1,mx[N];
char s[15]; vector<int>g[N];
void inc(int &x,int y){x+=y; if(x>=M) x-=M;}
int calc(char c){
if(c=='A') return 0;
if(c=='T') return 1;
if(c=='C') return 2;
if(c=='G') return 3; return -1;
}int main(){
scanf("%d%d",&ln,&n),getchar();
for(int i=1;i<=n;i++){
scanf("%s",s+1),getchar();
int ln=strlen(s+1),u=1;
for(int j=1;j<=ln;j++){
int ch=calc(s[j]);
if(!tr[u][ch]) tr[u][ch]=(++num);
u=tr[u][ch];
}mx[u]=ln;
}queue<int>q; q.push(1);
for(int i=0;i<26;i++) tr[0][i]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<26;i++){
if(!tr[u][i]) tr[u][i]=tr[fail[u]][i];
else{
q.push(tr[u][i]);
fail[tr[u][i]]=tr[fail[u]][i];
}
}mx[u]=max(mx[u],mx[fail[u]]);
}f[0][1][0]=1; int ans=0;
for(int i=0;i<ln;i++){
int o=(i&1);
for(int j=0;j<=num;j++) for(int k=0;k<=10;k++)
for(int c=0;c<4;c++){
int u=tr[j][c],rem=k-mx[u]+1;
if(rem<=0) inc(f[o^1][u][0],f[o][j][k]);
else inc(f[o^1][u][k+1],f[o][j][k]);
}memset(f[o],0,sizeof(f[o]));
}for(int i=0;i<=num;i++) inc(ans,f[ln&1][i][0]);
return !printf("%d\n",ans);
}
```