首页 > 代码库 > BZOJ 1030 [JSOI2007]文本生成器（AC自动机）
BZOJ 1030 [JSOI2007]文本生成器（AC自动机）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1030
【题目大意】
求出包含任意一个给定串的串数量
【题解】
我们求出不包含任意一个给定串的数量，用全集去减即可，
对于给定串建立AC自动机，用1节点作为根，0节点向1连全字符集转移作为超级源，
那么0->match能匹配所有不包含给定串的串，
记dp[i][j]表示匹配了i长度，匹配到AC自动机j节点的串数量，
统计之后取补集即可。
【代码】
#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=30010;namespace AC_DFA{ const int Csize=26; int tot,son[N][Csize],sum[N],fail[N],q[N],match[N]; void Initialize(){ memset(match,0,sizeof(int)*(tot+1)); memset(fail,0,sizeof(int)*(tot+1)); memset(sum,0,sizeof(int)*(tot+1)); for(int i=0;i<=tot;i++)for(int j=0;j<Csize;j++)son[i][j]=0; tot=1; } inline int Tr(char ch){return ch-‘A‘;} int Insert(char *s){ int x=1; for(int l=strlen(s),i=0,w;i<l;i++){ if(!son[x][w=Tr(s[i])]){ son[x][w]=++tot; }x=son[x][w]; }sum[x]++; return x; } void MakeFail(){ int h=1,t=0,i,j,x=1; q[++t]=1; while(h<=t)for(x=q[h++],i=0;i<Csize;i++) if(son[x][i]){ fail[son[x][i]]=son[fail[x]][i],q[++t]=son[x][i]; match[son[x][i]]=sum[son[x][i]]?son[x][i]:match[fail[son[x][i]]]; }else son[x][i]=son[fail[x]][i]; }}using namespace AC_DFA;const int P=10007;int dp[110][N];char s[N];void Dp(int x){ for(int i=1;i<=tot;i++){ if(match[i]||!dp[x-1][i])continue; for(int j=0;j<Csize;j++){ int k=i; while(!son[k][j])k=fail[k]; dp[x][son[k][j]]=(dp[x][son[k][j]]+dp[x-1][i])%P; } }}int n,m; int main(){ scanf("%d%d",&n,&m); Initialize(); for(int i=0;i<Csize;i++)son[0][i]=1; for(int i=1;i<=n;i++){scanf("%s",s);Insert(s);} MakeFail(); int ans1=0,ans2=1; dp[0][1]=1; for(int i=1;i<=m;i++)Dp(i); for(int i=1;i<=m;i++)ans2=(ans2*26)%P; for(int i=1;i<=tot;i++)if(!match[i])ans1=(ans1+dp[m][i])%P; printf("%d\n",(ans2-ans1+P)%P); return 0;}BZOJ 1030 [JSOI2007]文本生成器（AC自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。