题解 | 信息学奥赛一本通 文本生成器

第一道在AC自动机上DP的题，纪念纪念。

首先可以发现答案就是所有串的个数减去不包含可读串的串的个数。

前半部分是 26^m。后半部分使用DP求解。

首先建出可读串的AC自动机。

令 dp[i][j] 表示串长为 i，在AC自动机上走到编号为 j 的节点的合法串个数。

如果走到 j 的儿子 k 这个节点的串合法，那么就可以从 (i,j) 转移到(i+1,ch[j][k])。

dp[i+1][ch[j][k]]+=dp[i][j](0\le k<26)初始状态 dp[0][0]=1。答案为所有 dp[m][i] 的最大值。

可能看到这里，你最大的疑问就是：如何判断走到点 j 的串是否合法？真的可行吗？

想一想在AC自动机的fail的性质。我们就可以发现：如果从点 j 不停沿fail往上跳，经过的所有点（包括 j）没有串尾的节点，那么 j 合法，否则不合法。

这个合法性可以在BFS求fail时顺带求出。

（仔细想一想在AC自动机上跑匹配的本质就明白了）

时间复杂度 ，空间复杂度 ，全都带一个 26 的常数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    char ch=getchar();int x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
int n,m,cnt,q[6666],h,r,ch[6666][26],dp[111][6666],fail[6666];
bool war[6666];    //war表示节点是否不合法（不合法！不合法！）
char str[111];
void insert(char str[],int len){
    int now=0;
    FOR(i,1,len){
        int p=str[i]-'A';
        if(!ch[now][p]) ch[now][p]=++cnt;
        now=ch[now][p];
    }
    war[now]=true;    //串尾不合法
}
void build(){
    h=1;r=0;
    FOR(i,0,25) if(ch[0][i]) q[++r]=ch[0][i];
    while(h<=r){
        int u=q[h++];
        FOR(i,0,25) if(ch[u][i]){
            fail[ch[u][i]]=ch[fail[u]][i];
            war[ch[u][i]]|=war[fail[ch[u][i]]];
            //如果fail不合法，自己也不合法
            q[++r]=ch[u][i];
        }
        else ch[u][i]=ch[fail[u]][i];
    }
}
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) ans=ans*a%mod;
    return ans;
}
int main(){
    n=read();m=read();
    FOR(i,1,n) scanf("%s",str+1),insert(str,strlen(str+1));
    build();
    dp[0][0]=1;
    FOR(i,0,m-1) FOR(j,0,cnt) FOR(k,0,25)
        if(!war[ch[j][k]]) dp[i+1][ch[j][k]]=(dp[i+1][ch[j][k]]+dp[i][j])%mod;
        //ch[j][k]合法，可以转移
    int ans=qpow(26,m);
    FOR(i,0,cnt) ans=(ans-dp[m][i]+mod)%mod;    //容斥一下
    printf("%d\n",ans);    //答案
}