链接:hdu6138
题解
- 多记录一个深度,用第一个串进行匹配,沿途做标记,第二个串匹配的时候更新答案
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
using namespace std;
const int N=1e5+7;
int tr[N][26],id[N],fail[N],deep[N],flag[N],ans,T,n,x,y,cnt,m;
string a[N];
inline void build(string &str,int len){
int now=0;
rep(i,1,len){
int k=str[i-1]-'a';
if(!tr[now][k])tr[now][k]=++cnt;
deep[tr[now][k]]=deep[now]+1;
now=tr[now][k];
}
}
inline void pre(){
queue<int> q;
q.push(0);
fail[0]=-1;
while(!q.empty()){
int k=q.front();q.pop();
rep(i,0,25)if(tr[k][i]){
int son=tr[k][i],p=fail[k];
while(p>=0&&!tr[p][i])p=fail[p];
fail[son]=p>=0?tr[p][i]:0;
q.push(son);
}
}
}
inline void update(string &str,int len,int op){
int now=0;
rep(i,1,len){
int k=str[i-1]-'a',p=now;
while(p>=0&&!tr[p][k])p=fail[p];
now=p>=0?tr[p][k]:0;
int tmp=now;
if(op)while(tmp){flag[tmp]=1;tmp=fail[tmp];}
else while(tmp){
if(flag[tmp])ans=max(ans,deep[tmp]);tmp=fail[tmp];}
if(!op&&flag[now])ans=max(ans,deep[now]);
if(op)flag[now]=1;
}
}
int main(){
ios::sync_with_stdio(false);
cin>>T;
while(T--){
memset(tr,0,sizeof(tr));
memset(fail,0,sizeof(fail));
memset(deep,0,sizeof(deep));
cin>>n;cnt=0;
rep(i,1,n){cin>>a[i];
build(a[i],a[i].size());}
pre();
cin>>m;
while(m--){
memset(flag,0,sizeof(flag));
ans=0;
cin>>x>>y;
update(a[x],a[x].size(),1);
update(a[y],a[y].size(),0);
cout<<ans<<endl;
}
}
return 0;
}