首页 > 代码库 > POJ 1625 Censored!(AC自动机，DP)
POJ 1625 Censored!(AC自动机，DP)
http://poj.org/problem?id=1625
Censored!
Description The alphabet of Freeland consists of exactly N letters. Each sentence of Freeland language (also known as Freish) consists of exactly M letters without word breaks. So, there exist exactly N^M different Freish sentences. But after recent election of Mr. Grass Jr. as Freeland president some words offending him were declared unprintable and all sentences containing at least one of them were forbidden. The sentence S contains a word W if W is a substring of S i.e. exists such k >= 1 that S[k] = W[1], S[k+1] = W[2], ...,S[k+len(W)-1] = W[len(W)], where k+len(W)-1 <= M and len(W) denotes length of W. Everyone who uses a forbidden sentence is to be put to jail for 10 years. Find out how many different sentences can be used now by freelanders without risk to be put to jail for using it. Input The first line of the input file contains three integer numbers: N -- the number of letters in Freish alphabet, M -- the length of all Freish sentences and P -- the number of forbidden words (1 <= N <= 50, 1 <= M <= 50, 0 <= P <= 10). The second line contains exactly N different characters -- the letters of the Freish alphabet (all with ASCII code greater than 32). The following P lines contain forbidden words, each not longer than min(M, 10) characters, all containing only letters of Freish alphabet. Output Output the only integer number -- the number of different sentences freelanders can safely use. Sample Input 2 3 1 ab bb Sample Output 5 Source Northeastern Europe 2001, Northern Subregion |
题意：
给出一n种字符的字典，有k个禁用的单词，问能组成多少个不同的长度为m的合法字符串。
分析：
构建出AC自动机后在里面走m步有不经过单词结点有多少种方案，用dp[i][j]表示走了i步到第j个结点的方案数，根据计数原理可得状态转移方程:dp[i][j]=sum(dp[i][last_j]),其中last_j表示能走到j结点的前趋们，j不为单词结点。要注意此题要用到高精度，而且要用unsigned char存储。
/*
*
* Author : fcbruce <fcbruce8964@gmail.com>
*
* Time : Thu 20 Nov 2014 11:43:12 AM CST
*
*/
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10
#ifdef _WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define maxm
#define maxn 512
using namespace std;
unsigned char dict[64],P[16];
char str[233];
int q[maxn];
const int maxl = 16;
struct bign
{
static int width;
static long long mod;
int len;
long long s[maxl];
bign()
{
memset(s,0,sizeof s);
len=1;
}
bign operator = (int num)
{
char s[maxl];
sprintf(s,"%d",num);
*this=s;
return *this;
}
bign operator = (const char *s)
{
int l=strlen(s);
len=0;
for (int i=l-1;i>=0;i-=width,len++)
{
(*this).s[len]=0;
for (int j=max(0,i-width+1);j<=i;j++)
(*this).s[len]=(*this).s[len]*10+s[j]-'0';
}
return *this;
}
void str(char *s)
{
char format[10];
sprintf(format,"%%0%d%s",width,lld+1);
for (int i=len-1,j=0;i>=0;i--,j++)
sprintf(s+j*width,format,(*this).s[i]);
int j=0;
while (s[j]=='0' && s[j+1]!='\0') j++;
strcpy(s,s+j);
}
bign operator + (const bign &b)const
{
bign c;
c.len=0;
long long g=0ll;
for (itn i=0;g!=0ll || i<max(len,b.len);i++)
{
long long x=g;
if (i<len) x+=s[i];
if (i<b.len) x+=b.s[i];
c.s[c.len++]=x%mod;
g=x/mod;
}
return c;
}
}dp[2][maxn];
int bign::width=8;
long long bign::mod=100000000ll;
const int maxsize = 50;
struct ACauto
{
int ch[maxn][maxsize];
bool val[maxn];
int nex[maxn];
int sz,maxs;
ACauto()
{
memset(ch[0],0,sizeof ch[0]);
val[0]=false;
sz=1;
}
int idx(unsigned char c)
{
for (int i=0;i<maxs;i++)
if (dict[i]==c) return i;
return -1;
}
void insert(const unsigned char *s)
{
int u=0;
for (int i=0;s[i]!='\0';i++)
{
int c=idx(s[i]);
if (ch[u][c]==0)
{
memset(ch[sz],0,sizeof ch[sz]);
val[sz]=false;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=true;
}
void get_fail()
{
int f=0,r=-1;
nex[0]=0;
for (int c=0;c<maxs;c++)
{
int u=ch[0][c];
if (u!=0)
{
nex[u]=0;
q[++r]=u;
}
}
while (f<=r)
{
int x=q[f++];
for (int c=0;c<maxs;c++)
{
int u=ch[x][c];
if (u==0)
{
ch[x][c]=ch[nex[x]][c];
continue;
}
q[++r]=u;
int v=nex[x];
nex[u]=ch[v][c];
val[u]|=val[nex[u]];
}
}
}
bign DP(int l)
{
for (int i=0;i<sz;i++) dp[0][i]=0;
dp[0][0]=1;
int x=1;
for (int i=0;i<l;i++,x^=1)
{
for (int j=0;j<sz;j++) dp[x][j]=0;
for (int j=0;j<sz;j++)
{
for (int c=0;c<maxs;c++)
{
if (val[ch[j][c]]) continue;
dp[x][ch[j][c]]=dp[x][ch[j][c]]+dp[x^1][j];
}
}
}
bign total;
for (int i=0;i<sz;i++)
total=total+dp[x^1][i];
return total;
}
}acauto;
void read(unsigned char *P)
{
int i=0;
while ((P[i]=getchar())!='\n') i++;
P[i]=0;
}
int main()
{
#ifdef FCBRUCE
freopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCE
int n,m,p;
scanf("%d%d%d",&n,&m,&p);getchar();
acauto.maxs=n;
for (int i=0;i<n;i++) dict[i]=getchar();
getchar();
for (int i=0;i<p;i++)
{
read(P);
acauto.insert(P);
}
acauto.get_fail();
acauto.DP(m).str(str);
printf("%s\n",str);
return 0;
}
POJ 1625 Censored!(AC自动机，DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。