首页 > 代码库 > 【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—文本生成器