CF86C Genetic engineering解题报告

解题报告

CF86C Genetic engineering解题报告：

更好的阅读体验

题意

• 给定$n$个由ATCG组成的字符串，求构造一个长度为$m$的字符串，使得所有字符串可以通过匹配覆盖整个新字符串，求方案总数。
• $1\leqslant n\leqslant 10,1\leqslant m\leqslant 10^3$，给出的串长不超过$10$，对$10^9+7$取模。

分析

一道较套路的AC自动机dp题，但我没想出来/kk。

考虑先对所有给出的字符串建出AC自动机。

套路地设状态$f_{i,j}$为在AC自动机上匹配到了位置$j$，且已经用了$i$个字符的方案总数。

我们发现在AC自动机上转移边分为trie树上原有的转移边和AC自动机添加的转移边，考虑直接在上面dp，可以正常进行trie树边的转移，对于AC自动机的转移，我们能转移当且仅当当前结点是一个字符串结束位置。

上面的转移方式乍一看好像没错，因为转移AC自动机添加的转移边时需要跳fail边，变成原来匹配串的后缀，因此会让一些没有覆盖的点无法覆盖。

但是我们考虑一种情况：先通过trie树上的匹配到了一个结束位置$x$，然后往下跳一次trie树边，并跳一次AC自动机添加的转移边，最后再跳一次到了另一个位置较深的结束位置。

这样这个结束位置的长度足以覆盖前面没有覆盖的内容，这种方式仍然是合法的。

也就是说，我们跳fail边时，可能去除的前缀已经覆盖过了，因此这样的状态是不能转移的。

考虑另一种状态设计方式：$f_{i,j,k}$表示在AC自动机上匹配到了位置$k$，用了$i$个字符，且后$j$个字符还没有覆盖的方案数。

我们定义一个辅助数组$len_x$，表示到了AC自动机上的位置$x$，以$x$为结尾的最长字符串长度为多少。

这样的转移也非常清晰：我们当前的状态为$i,j,k$，通过AC自动机的转移边（无论是trie树边还是AC自动机新添加的转移边）转移到了点$x$，那么我们有：

• 当$len_x>j$时，$f_{i,j,k}\rightarrow f_{i+1,0,x}$
• 否则，$f_{i,j,k}\rightarrow f_{i+1,j+1,x}$

时间复杂度：$O(nm|S|)$。

代码

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=105,maxk=4,maxl=12,mod=1000000009,maxm=1005;
int n,m,tot,ans,maxlen;
int chd[maxn][maxk],fail[maxn],f[maxm][maxl][maxn],dep[maxn],len[maxn];
string s;
queue<int>q;
inline int get(char c){
    return c=='A'? 0:(c=='C'? 1:(c=='G'? 2:3));
}
void insert(string s){
    int now=1;
    for(int i=0;i<s.size();now=chd[now][get(s[i])],i++)
        if(chd[now][get(s[i])]==0)
            chd[now][get(s[i])]=++tot,dep[tot]=dep[now]+1;
    len[now]=dep[now];
}
void getfail(){
    while(!q.empty())
        q.pop();
    for(int i=0;i<=3;i++){
        if(chd[1][i])
            q.push(chd[1][i]),fail[chd[1][i]]=1;
        else chd[1][i]=1;
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<=3;i++){
            if(chd[x][i])
                q.push(chd[x][i]),fail[chd[x][i]]=chd[fail[x]][i];
            else chd[x][i]=chd[fail[x]][i];
        }
        len[x]=max(len[x],len[fail[x]]);
    }
}
void dp(){
    f[0][0][1]=1;
    for(int i=0;i<m;i++)
        for(int j=0;j<=maxlen;j++)
            for(int k=1;k<=tot;k++)
                if(f[i][j][k])
                    for(int p=0;p<=3;p++){
                        int x=chd[k][p];
                        if(len[x]>j)
                            f[i+1][0][x]=(f[i+1][0][x]+f[i][j][k])%mod;
                        else f[i+1][j+1][x]=(f[i+1][j+1][x]+f[i][j][k])%mod;
                    }
}
int main(){
    tot=1;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        cin>>s,maxlen=max(maxlen,(int)s.size());
        insert(s);
    }
    getfail();
    dp();
    for(int i=1;i<=tot;i++)
        ans=(ans+f[m][0][i])%mod;
    printf("%d\n",ans);
    return 0;
}