首页 > 代码库 > 【BZOJ】1030: [JSOI2007]文本生成器(递推+ac自动机)
【BZOJ】1030: [JSOI2007]文本生成器(递推+ac自动机)
http://www.lydsy.com/JudgeOnline/problem.php?id=1030
其实做了1009也不会感到很难了,无非将kmp变成了ac自动机。
设f[i,j]表示前i个串当前匹配到j的节点的方案数。。
然后自己想。
sb错1:ac自动机的节点开小了(自己想错了。。以为最多节点就是层数×分支(26)。。。。于是。。其实是n个串的长度和。。。)
sb错2:ac自动机bfs时没有维护信息啊!!只维护了一个fail。。。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const int N=102, M=N*60, Q=M+M, MD=10007;int c[M][26], tot, w[M], q[M], fail[M], n, f[N][M];void add(char *s) { int len=strlen(s), now=0; rep(i, len) { int t=s[i]-‘A‘; if(!c[now][t]) c[now][t]=++tot; now=c[now][t]; } w[now]=1;}void bfs() { int now=0, front=0, tail=0; q[tail++]=now; while(front!=tail) { now=q[front++]; if(front==Q) front=0; rep(y, 26) if(c[now][y]) { q[tail++]=c[now][y]; if(tail==Q) tail=0; if(now==0) continue; int t=fail[now]; while(t && !c[t][y]) t=fail[t]; fail[c[now][y]]=c[t][y]; if(w[c[t][y]]) w[c[now][y]]=1; //这里。。。。。。。。。 } }}void P(int &a, const int &b) { a=(a+b)%MD; }int work() { int ret=0; // rep(i, 26) { //一开始我这样写的,可以对,从i=1开始就行了 // if(!c[0][i]) f[1][0]++; // else if(!w[c[0][i]]) f[1][c[0][i]]=1; // } f[0][0]=1; //这是后边看了题解后才焕然大雾。。 for1(i, 0, n) for1(j, 0, tot) if(f[i][j]) { rep(y, 26) { int t=j; while(t && !c[t][y]) t=fail[t]; t=c[t][y]; if(!w[t]) P(f[i+1][t], f[i][j]); } } for1(i, 0, tot) if(!w[i]) P(ret, f[n][i]); int all=1; for1(i, 1, n) all*=26, all%=MD; ret=((all-ret)%MD+MD)%MD; return ret;}int main() { int m=getint(); read(n); char s[N]; for1(i, 1, m) { scanf("%s", s); add(s); } bfs(); print(work()); return 0;}
Description
JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。 ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?
Input
输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固定长度M;以下N行,每一行包含一个使用者了解的单词。 这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A..Z 。
Output
一个整数,表示可能的文章总数。只需要知道结果模10007的值。
Sample Input
A
B
Sample Output
HINT
Source
【BZOJ】1030: [JSOI2007]文本生成器(递推+ac自动机)