Fork me on GitHub

Uoj#43.【清华集训2014】Router

Uoj#43. 【清华集训2014】Router

题意:

  • 实现一个支持部分正则表达式的$\rm router$。

题解:

  • 直接匹配很简单,直接考虑构建$\rm NFA$来匹配每个正则表达式。
  • 首先对于每个$Alternative$,每个都是可以匹配的,括号可以一层一层拆开。
  • 然后将每个的结尾统一连向一个结束节点。
  • 对于$Alternative$内部,将各个$Term$连接即可。
  • 然后考虑$Term$,对于$Quantifier$,根据上下界分情况讨论:
    • 如果没有上界:
      • 若下界为$0$,设置从原先节点$p$匹配到的$np$的单个$Atom$匹配,然后加一条从$np$到$p$的无条件匹配边,结束节点从$p$连出一个新点。
      • 若下界存在(设为$l$),设置$l$个新节点$a_1,a_2,\cdots ,a_l$,其之间各自建立单个$Atom$的匹配,然后连一条从$a_l$到$a_{l-1}$的无条件匹配边,$a_l$为结束节点。
    • 如果上界存在(设为$r$),设置$r$个新节点$a_1,a_2,\cdots ,a_r$,同上建立匹配,然后从$a_l,a_{l+1},\cdots ,a_{r-1}$向$a_r$连一条无条件匹配边,$a_r$为结束节点。
  • 对于每个$Atom$:
    • 如果是(Regexp)的形式,去掉括号跑最早开始的过程。
    • 如果是一段字符区间或单个字符,正常连边即可。
  • 这样构建完了$\rm NFA$,匹配时暴力跑所有可能的边即可。
  • 输出的时候可以使用$\rm map$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
const int N=20009;
const int M=8009;
int trans[128];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
struct REG
{
int to[M][62],cnt,sink;
set<int> next[M];
void clear()
{
for (int i=1;i<=cnt;i++) next[i].clear();
memset(to,0,sizeof(to));
}
void init(string A)
{
sink=Regexp(A,cnt=1);
}
void add_edge(int x,int y)
{
next[x].insert(y);
}
int get(int x,int y)
{
return to[x][y]?to[x][y]:to[x][y]=++cnt;
}
int Atom(string A,int p)
{
if (A[0]=='(') return Regexp(A.substr(1,A.length()-2),p);
else
{
if (A[0]=='[')
{
int l=trans[A[1]],r=trans[A[3]];
int np=++cnt;
for (int i=l;i<=r;i++)
to[p][i]=np;
return np;
}
else
return get(p,trans[A[0]]);
}
}
void rep(string A,int *a,int ed)
{
for (int i=1;i<=ed;i++)
a[i]=Atom(A,a[i-1]);
}
int Alternative(string A,int p)
{
int a[29];
string B,empty;
int len=A.length();
memset(a,0,sizeof(a));
for (int i=0;i<len;)
{
int j=i,deep=0;
B=empty;
if (A[i]=='[')
for (;i<len;i++)
{
if (A[i]=='[') deep++;
else
if (A[i]==']')
if (!(--deep)) break;
}
else if (A[i]=='(')
for (;i<len;i++)
{
if (A[i]=='(') deep++;
else
if (A[i]==')')
if (!(--deep)) break;
}
B=A.substr(j,i-j+1);
i++;
if (A[i]=='{')
{
int l=0,r=0;
for (i++;A[i]>='0'&&A[i]<='9';i++)
l=l*10+A[i]-'0';
i++;
if (A[i]=='}')
{
i++,a[0]=p;
if (!l)
{
rep(B,a,1);
add_edge(a[1],a[0]),add_edge(a[0],p=++cnt);
}
else
{
rep(B,a,l);
add_edge(a[l],a[l-1]),p=a[l];
}
}
else
{
for (;A[i]>='0'&&A[i]<='9';i++)
r=r*10+A[i]-'0';
i++,a[0]=p;
rep(B,a,r);
for (int k=l;k<r;k++) add_edge(a[k],a[r]);
p=a[r];
}
}
else p=Atom(B,p);
}
return p;
}
int Regexp(string A,int p)
{
string B,empty;
vector<int> ret;
set<int> now;
bool flag=0;
int len=A.length(),deep=0,Ret;
A+='|',len++;
for (int i=0;i<len;i++)
{
if (A[i]=='('||A[i]=='['||A[i]=='{') deep++;
if (A[i]==')'||A[i]==']'||A[i]=='}') deep--;
if (!deep&&A[i]=='|')
{
add_edge(p,++cnt);
int r=Alternative(B,cnt);
ret.push_back(r);
if (!flag) flag=1,now=next[r];
else
for (int j:now)
if (next[r].find(j)==next[r].end()) now.erase(j);
B=empty;
}
else B+=A[i];
}
if (now.empty())
{
Ret=++cnt;
for (int i:ret) add_edge(i,Ret);
}
else Ret=*now.begin();
return Ret;
}
int a[M],b[M],T,vis[M];
bool match(string A)
{
int len=A.length();
int n=1,m=0;
vis[a[n]=1]=++T;
for (int j=1;j<=n;j++)
for (int i:next[a[j]])
if (vis[i]!=T) vis[i]=T,a[++n]=i;
for (int i=0;i<len;i++)
{
int tr=trans[A[i]];
++T,m=0;
for (int j=1;j<=n;j++)
if (to[a[j]][tr]&&vis[to[a[j]][tr]]!=T)
vis[to[a[j]][tr]]=T,b[++m]=to[a[j]][tr];
for (int j=1;j<=m;j++)
for (int k:next[b[j]])
if (vis[k]!=T) vis[k]=T,b[++m]=k;
n=m;
for (int j=1;j<=n;j++)
a[j]=b[j];
}
return vis[sink]==T;
}
}Reg[59];
int n,m,cnt,reg_num;
string path[N],action[N],reg_name[N];
int to[N*10][59],Id[N*10];
map<string,string> reg;
map<string,int> reg_id,To[N*10];
int Get(int x,string A)
{
return To[x].count(A)?To[x][A]:To[x][A]=++cnt;
}
int get(int x,int y)
{
return to[x][y]?to[x][y]:to[x][y]=++cnt;
}
void ins(string A,int id)
{
string B,empty;
int len=A.length(),now=1;
bool flag=0;
for (int i=1;i<=len;i++)
if (i==len||A[i]=='/')
{
if (flag) flag=0,now=get(now,reg_id[B]);
else now=Get(now,B);
B=empty;
}
else if (A[i]==':') flag=1;
else B+=A[i];
Id[now]=id;
}
void qry(string A)
{
string B,empty;
int len=A.length(),now=1;
map<string,vector<string> > mp;
mp.clear();
int POS=0;
for (int i=1;i<=len;i++)
if (i==len||A[i]=='/'||A[i]=='?')
{
if (To[now].count(B)) now=To[now][B];
else
{
int pos=0;
for (int j=1;j<=reg_num;j++)
if (to[now][j])
if (Reg[j].match(B))
{
now=to[now][j];
pos=j;
break;
}
if (!pos)
{
puts("404 Not Found");
return;
}
mp[reg_name[pos]].push_back(B);
}
if (A[i]=='?')
{
POS=i+1;
break;
}
B=empty;
}
else B+=A[i];
int Ans=Id[now];
if (!now) puts("404 Not Found");
else
{
cout<<"Request matches action \""<<action[Ans];
cout<<"\" with parameters {";
if (POS)
{
len++,A+="&";
string a,b;
for (int i=POS;i<len;i++)
{
if (A[i]=='=') a=b,b=empty;
else if (A[i]=='&') mp[a].push_back(b),a=b=empty;
else b+=A[i];
}
}
bool flag=0;
for (auto Now:mp)
{
if (flag) putchar(',');
else flag=1;
putchar('"');
cout<<Now.first;
putchar('"'),putchar(':');
if (Now.second.size()>1) putchar('[');
bool fl=0;
for (auto i:Now.second)
{
if (fl) putchar(',');
else fl=1;
putchar('"');
cout<<i;
putchar('"');
}
if (Now.second.size()>1) putchar(']');
}
puts("}");
}
}
void work()
{
n=read();
for (int i=0;i<59;i++) Reg[i].clear();
for (int i=0;i<N*10;i++) To[i].clear();
reg.clear(),reg_id.clear();
reg_num=cnt=0;
memset(to,0,sizeof(to));
memset(Id,0,sizeof(Id));
for (int i=1;i<=n;i++)
cin>>path[i]>>action[i];
string A,B;
while (1)
{
cin>>A;
if (A[0]>='0'&&A[0]<='9')
{
m=A[0]-'0';
for (int i=1;i<A.length();i++)
m=m*10+A[i]-'0';
break;
}
cin>>B;
reg[A]=B;
Reg[reg_id[A]=++reg_num].init(B);
reg_name[reg_num]=A;
}
cnt=1;
for (int i=1;i<=n;i++)
ins(path[i],i);
while (m--)
{
cin>>A;
qry(A);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
for (int i='0';i<='9';i++) trans[i]=cnt++;
for (int i='a';i<='z';i++) trans[i]=cnt++;
for (int i='A';i<='Z';i++) trans[i]=cnt++;
int T=read();
for (int i=1;i<=T;i++)
{
printf("Case #%d:\n",i);
work();
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#43.【清华集训2014】Router

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj43/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。