程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj1030【JSOI2007】文本生成器

bzoj1030【JSOI2007】文本生成器

編輯:C++入門知識

bzoj1030【JSOI2007】文本生成器


 

1030: [JSOI2007]文本生成器

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2891 Solved: 1193
[Submit][Status][Discuss]

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

2 2
A
B

Sample Output

100

HINT

Source

畢竟是自己做的第一道AC自動機題,還是小小地慶祝一下吧……

我們假設在Trie樹中表示單詞結尾的節點為結尾點。

在添加失配邊後,Trie樹就轉化成一個有向圖,問題也就轉化成:從起點出發,走m步,至少路過一個結尾點的方案數。

這就可以用動態規劃來實現了。具體方法如下:

用f[i][j][0]表示走i步到達j點不經過結尾點的方案數,用f[i][j][1]表示走i步到達j點經過結尾點的方案數。

我們很容易可以想到狀態轉移方程。(詳見程序)

最終答案為∑(i)f[m][i][1],注意每次計算後都要取模。

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define mod 10007
using namespace std;
int t[6010][26],f[110][6010][2],v[6010],go[6010];
int n,m,tot;
char s[110];
queue q;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void insert()
{
	scanf("%s",s+1);
	int len=strlen(s+1),now=1;
	F(i,1,len)
	{
		int x=s[i]-'A';
		if (!t[now][x]) t[now][x]=++tot;
		now=t[now][x];
	}
	v[now]=1;
}
inline void bfs()
{
	q.push(1);
	while (!q.empty())
	{
		int x=q.front(),y,j;q.pop();v[x]|=v[go[x]];
		F(i,0,25)
		{
			j=go[x];
			while (j&&!t[j][i]) j=go[j];
			if (t[x][i])
			{
				go[y=t[x][i]]=j?t[j][i]:1;
				q.push(y);
			}
			else t[x][i]=j?t[j][i]:1;
		}
	}
}
inline void dp()
{
	f[0][1][0]=1;
	F(i,0,m) F(j,1,tot) F(k,0,25) F(l,0,1)
	{
		if (v[t[j][k]]) (f[i+1][t[j][k]][1]+=f[i][j][l])%=mod;
		else (f[i+1][t[j][k]][l]+=f[i][j][l])%=mod;
	}
}
int main()
{
	n=read();m=read();tot=1;
	F(i,1,n) insert();
	bfs();
	dp();
	int ans=0;
	F(i,1,tot) (ans+=f[m][i][1])%=mod;
	printf("%d\n",ans);
	return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved