[HEOI2016/TJOI2016]字符串 题解

题目链接

题目大意

​ 给一个串,每次询问a b c d,求 $S[a…b]$ 的所有子串与 $S[c…d]$ 的最长公共前缀。

题目解法

​ 发现这个答案较难直接计算,考虑二分答案。每次二分最长公共前缀为 $x$ ,然后考虑如何判定。存在一个长为 $x$ 的公共前缀,当且仅当存在一个 $S$ 的左端点在$[a…b-x+1]$中的后缀是$S[c…c+x]$的前缀。两个限定条件可以采用在后缀树上可持久化线段树合并计算。

代码

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
#include <bits/stdc++.h>
#define maxn 200005
int n,q,a,b,c,d,ch[maxn<<6][2],root[maxn]={0},anc[maxn][19]={0},depth[maxn]={0},rank[maxn],tail=0;
char s[maxn];

const int inf=1e8;
struct suffixTree {
int link[maxn<<1],len[maxn<<1],start[maxn<<1],s[maxn<<1],n,tail,now,rem,ch[maxn<<1][27];
suffixTree ():tail(1),n(0),rem(0),now(1) {len[0]=inf;}
int newnode(int st,int le){
link[++tail]=1;start[tail]=st;len[tail]=le;return tail;
}
void extend(int x){
s[++n]=x;rem++;
for (int last=1;rem;){
while (rem>len[ch[now][s[n-rem+1]]]) rem-=len[now=ch[now][s[n-rem+1]]];
int &v=ch[now][s[n-rem+1]];int c=s[start[v]+rem-1];
if (!v||x==c){
link[last]=now;last=now;
if (!v) v=newnode(n-rem+1,inf);
else break;
}else{
int u=newnode(start[v],rem-1);
ch[u][c]=v;ch[u][x]=newnode(n,inf);
start[v]+=rem-1;len[v]-=rem-1;
link[last]=v=u;last=u;
} if (now==1) rem--;else now=link[now];
}
}
}sft;

int insert(int rt,int l,int r,int p){
int nrt=++tail;
ch[nrt][0]=ch[rt][0];ch[nrt][1]=ch[rt][1];
if (l==r)return nrt;
int mid=(l+r)>>1;
if (p<=mid)ch[nrt][0]=insert(ch[rt][0],l,mid,p);
else ch[nrt][1]=insert(ch[rt][1],mid+1,r,p);
return nrt;
}

int merge(int u,int v){
if (!u||!v)return u+v;
int nrt=++tail;
ch[nrt][0]=merge(ch[u][0],ch[v][0]);
ch[nrt][1]=merge(ch[u][1],ch[v][1]);
return nrt;
}

int query(int rt,int L,int R,int l,int r){
if (l>R||r<L||!rt)return 0;
if (l<=L&&R<=r)return 1;
return query(ch[rt][0],L,(L+R)>>1,l,r)||query(ch[rt][1],((L+R)>>1)+1,R,l,r);
}

void dfs(int u,int f){
anc[u][0]=f;
for (int i=1;i<=17;++i)anc[u][i]=anc[anc[u][i-1]][i-1];
int len=std::min(sft.len[u],n-sft.start[u]+1),isleaf=1;
depth[u]=depth[f]+len;
for (int i=0;i<=26;++i){
if (sft.ch[u][i]){
dfs(sft.ch[u][i],u);
root[u]=merge(root[u],root[sft.ch[u][i]]);
isleaf=0;
}
}if (isleaf){
root[u]=insert(root[u],1,n,n-depth[u]+1);
rank[n-depth[u]+1]=u;
}
}

int locate(int l,int r){
int u=rank[l];
for (int i=17;i>=0;i--)
if (depth[anc[u][i]]>=(r-l+1))u=anc[u][i];
return u;
}


int check(int x){
int u=locate(c,c+x-1);
if (query(root[u],1,n,a,b-x+1))return 1;
return 0;
}

int main(){
scanf("%d%d",&n,&q);
scanf("%s",s+1);
for (int i=1;i<=n;++i)sft.extend(s[i]-'a');sft.extend(26);
dfs(1,0);
while (q--){
scanf("%d%d%d%d",&a,&b,&c,&d);
int l=1,r=std::min(b-a+1,d-c+1),ans=0;
while (l<=r){
int mid=(l+r)>>1;
if (check(mid)){ans=mid;l=mid+1;}
else r=mid-1;
}printf("%d\n",ans);
}
return 0;
}