看懂题意就直接建图吧… 记个 \(fa\) 表示真正的前驱。

边是字符串,就 \(Trie\) 搞一搞,注意一下细节就好了。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005,maxe=200005;
int Q1,Q2,n,m,ans[maxn];
char st[maxn];
struct node{
node *ch[26],*fa; char v; int to;
node(int _v=0,node* _fa=0){ v=_v; fa=_fa; to=0; memset(ch,0,sizeof(ch)); }
} _poor[maxn], *p_top=_poor, *rt[maxn];
typedef node* P_node;
P_node newnode(int _v,P_node _fa){
(*p_top)=node(_v,_fa);
return p_top++;
}
P_node Travel(P_node p,char* &s){
for(;'a'<=(*s)&&(*s)<='z';s++){
if(!p->ch[(*s)-'a']) p->ch[(*s)-'a']=newnode(*s,p);
p=p->ch[(*s)-'a'];
}
return p;
}
int main(){
freopen("uoj13.in","r",stdin);
freopen("uoj13.out","w",stdout);
scanf("%d%d",&Q1,&Q2);
rt[m=1]=newnode('/',0);
while(Q1--){
scanf("%s",st);
int x=1; char* sp=st; P_node t1;
while(1){
sp++; t1=Travel(rt[x],sp);
if(!(*sp)) break;
if(!t1->to) t1->to=++m, rt[m]=newnode('/',t1);
x=t1->to;
}
scanf("%s",st);
x=1; sp=st;
if(strlen(st)>1)
while((*sp)){
sp++; P_node t2=Travel(rt[x],sp);
if(!t2->to) t2->to=++m, rt[m]=newnode('/',t2);
x=t2->to;
}
t1->to=x;
}
while(Q2--){
scanf("%s",st);
int x=1; char* sp=st;
if(strlen(st)>1)
while((*sp)){
sp++; P_node t=Travel(rt[x],sp);
if(!t->to) t->to=++m, rt[m]=newnode('/',t);
x=t->to;
}
if(x==1){ printf("/\n"); continue; }
P_node p=rt[x]->fa;
ans[0]=0; while(p) ans[++ans[0]]=p->v, p=p->fa;
for(int i=ans[0];i>=1;i--) putchar(ans[i]); printf("\n");
}
return 0;
}