首页 > 代码库 > BZOJ 1030 JSOI2007 文本生成器 AC自动机+DP
BZOJ 1030 JSOI2007 文本生成器 AC自动机+DP
题目大意:给定n个模式串,求长度为m的至少含有一个模式串的字符串共有多少种
照例,令f[i][j]表示长度为i的字符串与AC自动机上的第j个点匹配的方案数
直接DP很难,我们考虑补集法,即用26^m减去不含任何模式串的字符串的数量
后者就是经典的AC自动机DP模型啦~~
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD 10007 using namespace std; struct Trie{ Trie *son[26],*fail; bool ed; }*root,mempool[6060],*C=mempool; int n,m,ans; int f[110][6060]; char s[110]; void Insert(Trie* &p,char *s) { if(!p) p=C++; if(!*s) { p->ed=1; return ; } Insert(p->son[(*s)-'A'],s+1); } void Build_Tree() { static Trie *q[6060]; static int r,h; int i; for(i=0;i<26;i++) if(root->son[i]) root->son[i]->fail=root,q[++r]=root->son[i]; else root->son[i]=root; while(r!=h) { Trie *p=q[++h]; for(i=0;i<26;i++) if(p->son[i]) { p->son[i]->fail=p->fail->son[i]; p->son[i]->ed|=p->son[i]->fail->ed; q[++r]=p->son[i]; } else p->son[i]=p->fail->son[i]; } } int Quick_Power(int x,int y) { int re=1; while(y) { if(y&1) re*=x,re%=MOD; x*=x,x%=MOD; y>>=1; } return re; } int main() { int i,j,k; cin>>n>>m; for(i=1;i<=n;i++) scanf("%s",s),Insert(root,s); Build_Tree(); f[0][0]=1; for(i=0;i<m;i++) for(j=0;j<C-mempool;j++) if(!mempool[j].ed) for(k=0;k<26;k++) f[i+1][mempool[j].son[k]-mempool]+=f[i][j], f[i+1][mempool[j].son[k]-mempool]%=MOD; ans=Quick_Power(26,m); for(j=0;j<C-mempool;j++) if(!mempool[j].ed) ans+=MOD-f[m][j],ans%=MOD; cout<<ans<<endl; return 0; } //f[i][j]表示第i个字符对应AC自动机上的第j个节点且不含任何模式串的方案数
BZOJ 1030 JSOI2007 文本生成器 AC自动机+DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。