首页 > 代码库 > 【bzoj1030】 JSOI2007—文本生成器
【bzoj1030】 JSOI2007—文本生成器
http://www.lydsy.com/JudgeOnline/problem.php?id=1030 (题目链接)
题意
给出$n$个单词,问有多少个长度为$m$的文本中至少包含一个单词。
Solution
构造好AC自动机以后在上面dp,$f[i][j]$表示长度为$i$匹配到自动机上节点$j$时的没有被任意单词匹配的文本个数。转移枚举接在第$j+1$个位置的字符是哪一个,并且保证走过的节点没有一个是结束节点就可以了。
细节
0号节点为root。
代码
// bzoj1030#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf (1ll<<30)#define MOD 10007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxl=200,maxn=60;int n,m,sz=1,f[maxl][maxn*maxl];char s[maxl];struct node { int son[26],next,end; int& operator [] (int x) {return son[x];}}tr[maxn*maxl];namespace ACM { void insert(char *r) { int len=strlen(r+1),p=1; for (int i=1;i<=len;i++) { if (!tr[p][r[i]-‘A‘]) tr[p][r[i]-‘A‘]=++sz; p=tr[p][r[i]-‘A‘]; } tr[p].end=1; } void buildfail() { queue<int> q;q.push(1); tr[1].next=0; while (!q.empty()) { int x=q.front();q.pop(); for (int i=0;i<26;i++) if (tr[x][i]) { int k=tr[x].next; while (!tr[k][i]) k=tr[k].next; tr[tr[x][i]].next=tr[k][i]; tr[tr[x][i]].end|=tr[tr[k][i]].end; q.push(tr[x][i]); } } }}using namespace ACM; int main() { scanf("%d%d",&n,&m); for (int i=0;i<26;i++) tr[0][i]=1; for (int i=1;i<=n;i++) { scanf("%s",s+1); insert(s); } buildfail(); f[0][1]=1; for (int i=0;i<m;i++) for (int j=1;j<=sz;j++) if (f[i][j]) { for (int k=0;k<26;k++) { int p=j; while (!tr[p][k]) p=tr[p].next; p=tr[p][k]; if (!tr[p].end) (f[i+1][p]+=f[i][j])%=MOD; } } int sum=1,ans=0; for (int i=1;i<=m;i++) (sum*=26)%=MOD; for (int i=1;i<=sz;i++) (ans+=f[m][i])%=MOD; printf("%d\n",(sum-ans+MOD)%MOD); return 0;}
【bzoj1030】 JSOI2007—文本生成器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。