Censored!
Time Limit: 5000MS |
|
Memory Limit: 10000K |
Total Submissions: 5865 |
|
Accepted: 1569 |
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
伤不起啊
用c++交re到死
用g++交就过了
ac自动机+dp+高精度
伤不起啊
状态还是用trie图表示和转移
方程 f[i][j]=f[i][j]+f[i-1][k]*g[k][j];
g[k][j]表示从状态k转移到状态j的边数
1
#include <cstdio>
2
#include <cstdlib>
3
#include <cstring>
4
#include <cmath>
5
#include <ctime>
6
#include <cassert>
7
#include <iostream>
8
#include <sstream>
9
#include <fstream>
10
#include <map>
11
#include <set>
12
#include <vector>
13
#include <queue>
14
#include <algorithm>
15
#include <iomanip>
16
#define maxn 105
17
#define pp printf("here\n")
18
using namespace std;
19
struct node
20

{
21
int next[52];
22
int fail,count;
23
void init()
24
{
25
memset(next,-1,sizeof(next));
26
fail=-1;
27
count=0;
28
}
29
} s[1005];
30
struct bignum
31

{
32
#define MAXCOUNT 10000
33
#define maxlen 105
34
int x[maxlen];
35
int len;
36
// int zzz;
37
void init()
38
{
39
memset(x,0,sizeof(x));
40
// zzz=1;
41
}
42
} f[105][105];
43
int n,m,p,sind;
44
int hash[800];
45
int q[505],head,tail;
46
int g[105][105];
47
void print(bignum a)
48

{
49
cout<<a.x[a.len];
50
for(int i=a.len-1; i>=1; i--)
51
{
52
if(a.x[i]<1000) putchar('0');
53
if(a.x[i]<100) putchar('0');
54
if(a.x[i]<10) putchar('0');
55
printf("%d",a.x[i]);
56
}
57
printf("\n");
58
}
59
void mulanum(bignum &a,int b)
60

{
61
int x;
62
x=MAXCOUNT;
63
for(int i=1; i<=a.len; i++)
64
a.x[i]=a.x[i]*b;
65
for(int i=1; i<=a.len; i++)
66
{
67
a.x[i+1]+=a.x[i]/x;
68
a.x[i]=a.x[i]%x;
69
}
70
while(a.x[a.len+1]>0)
71
{
72
a.len++;
73
a.x[a.len+1]=a.x[a.len]/x;
74
a.x[a.len]%=x;
75
}
76
}
77
void addabignum(bignum &a,bignum b)
78

{
79
int x;
80
x=MAXCOUNT;
81
a.len=max(a.len,b.len);
82
// printf("%d\n",a.len);
83
for(int i=1; i<=a.len; i++)
84
a.x[i]=a.x[i]+b.x[i];
85
for(int i=1; i<=a.len; i++)
86
{
87
a.x[i+1]+=a.x[i]/x;
88
a.x[i]=a.x[i]%x;
89
}
90
while(a.x[a.len+1]>0)
91
{
92
a.len++;
93
a.x[a.len+1]=a.x[a.len]/x;
94
a.x[a.len]%=x;
95
}
96
}
97
void cas_init()
98

{
99
s[0].init();
100
sind=1;
101
}
102
void ins(char str[])
103

{
104
int i,j,ind;
105
int len=strlen(str);
106
ind=0;
107
for(int i=0;i<len;i++)
108
{
109
j=hash[str[i]+128];
110
if(s[ind].next[j]==-1)
111
{
112
s[sind].init();
113
s[ind].next[j]=sind++;
114
}
115
ind=s[ind].next[j];
116
}
117
s[ind].count++;
118
}
119
void make_fail()
120

{
121
int p,i,son,u;
122
head=0;
123
tail=1;
124
q[tail]=0;
125
while(head<tail)
126
{
127
u=q[++head];
128
for(i=0; i<n; i++)
129
{
130
if(s[u].next[i]!=-1)
131
{
132
p=s[u].fail;
133
son=s[u].next[i];
134
while(p!=-1&&s[p].next[i]==-1) p=s[p].fail;
135
if(u==0) s[son].fail=0;
136
else s[son].fail=s[p].next[i];
137
if(s[s[son].fail].count) s[son].count=1;
138
q[++tail]=son;
139
}
140
else
141
{
142
p=s[u].fail;
143
while(p!=-1&&s[p].next[i]==-1) p=s[p].fail;
144
if(u==0) s[u].next[i]=0;
145
else s[u].next[i]=s[p].next[i];
146
}
147
148
}
149
}
150
}
151
void make_mats()
152

{
153
int i,j,son;
154
memset(g,0,sizeof(g));
155
for(i=0; i<sind; i++)
156
{
157
if(s[i].count) continue;
158
for(j=0; j<n; j++)
159
{
160
son=s[i].next[j];
161
if(s[son].count) continue;
162
g[i][son]++;
163
}
164
}
165
}
166
void solve()
167

{
168
int son;
169
bignum tmp;
170
// pp;
171
for(int i=0;i<=m;i++)
172
{
173
for(int j=0;j<sind;j++)
174
f[i][j].init();
175
}
176
f[0][0].len=1;
177
f[0][0].x[1]=1;
178
for(int i=1; i<=m; i++)
179
{
180
for(int j=0; j<sind; j++)
181
{
182
if(s[j].count) continue;
183
//f[i][j].init();
184
f[i][j].len=1;
185
//for(int k=0; k<j; k++)
186
//if(s[k].count==0)
187
for(int k=0; k<sind; k++)
188
{
189
// son=s[j].next[k];
190
if(s[son].count) continue;
191
tmp=f[i-1][k];
192
//printf("tmp=");print(tmp);
193
mulanum(tmp,g[k][j]);
194
addabignum(f[i][j],tmp);
195
}
196
}
197
}
198
bignum res;
199
res.init();
200
res.len=1;
201
for(int i=0; i<sind; i++)
202
addabignum(res,f[m][i]);
203
print(res);
204
}
205
int main()
206

{
207
char str[105];
208
scanf("%d%d%d",&n,&m,&p);
209
cas_init();
210
gets(str);
211
// cout<<str<<endl;
212
gets(str);
213
for(int i=0;i<n;i++) hash[str[i]+128]=i;
214
for(int i=1; i<=p; i++)
215
{
216
gets(str);
217
ins(str);
218
}
219
make_fail();
220
make_mats();
221
solve();
222
return 0;
223
}
224
code