bzoj1030: [JSOI2007]文本生成器

本文主要是介绍bzoj1030: [JSOI2007]文本生成器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1030

思路：直接算好像比较困难，所以考虑先算不可读的串的个数，再拿总串数去减。

不可读的串的数量就是在AC自动机上走M步而不经过结尾节点（包括结尾点和fail指向结尾点的节点）的路径条数。

这个怎么求呢？

设f[i][j]表示走i步，现在在j号节点的路径条数。

那么f[i][j]可以转移f[i+1][son[j][k]]。

就是i+1个字符为k的状态。

最后把所有f[m][i]累和就是不可读的串。

#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=6000,maxm=105,mod=10007;
using namespace std;
int n,m,f[maxm][maxn],ans1=1,ans2;char s[maxn];struct AC_DFA{int tot,ch[maxn][26],fail[maxn],q[maxn],head,tail;bool dang[maxn];void insert(){int p=0,len=strlen(s);for (int i=0;i<len;p=ch[p][s[i]-'A'],i++) if (!ch[p][s[i]-'A']) ch[p][s[i]-'A']=++tot;dang[p]=1;}void getfail(){head=0,q[tail=1]=0,fail[0]=-1;while (head!=tail){int x=q[++head];for (int i=0;i<26;i++)if (ch[x][i]) q[++tail]=ch[x][i],fail[ch[x][i]]=x==0?0:ch[fail[x]][i];else ch[x][i]=x==0?0:ch[fail[x]][i];dang[x]|=dang[fail[x]];}}void work(){f[0][0]=1;for (int i=1;i<=m;i++)for (int j=0;j<=tot;j++){if (dang[j]) continue;for (int k=0;k<26;k++)f[i][ch[j][k]]=(f[i][ch[j][k]]+f[i-1][j])%mod;}for (int i=0;i<=tot;i++) if (!dang[i]) ans2+=f[m][i];for (int i=1;i<=m;i++) ans1=(ans1*26)%mod;printf("%d\n",((ans1-ans2)%mod+mod)%mod);}
}T;int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",s),T.insert();T.getfail(),T.work();return 0;
}

这篇关于bzoj1030: [JSOI2007]文本生成器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---