【bzoj1030】 JSOI2007—文本生成器

时间：2023-11-25 20:43:14

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;

}

相关文章