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")
18using namespace std;
19struct 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];
30struct 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];
43int n,m,p,sind;
44int hash[800];
45int q[505],head,tail;
46int g[105][105];
47void 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}
59void 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}
77void 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}
97void cas_init()
98{
99 s[0].init();
100 sind=1;
101}
102void 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}
119void 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}
151void 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}
166void 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}
205int 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