[后缀树 + 主席树] LOJ#2059. 「TJOI HEOI2016」字符串

后缀树找子串出现位置,用dfs序+主席树维护 \(firstpos\)

后缀树用SAM构建。找一个子串对应的节点需要倍增。具体见代码...

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400005,maxe=maxn;
int N_seg,ch[maxn*40][2],sum[maxn*40];
void maintain(int p){
sum[p]=sum[ch[p][0]]+sum[ch[p][1]];
}
int Build(int L,int R){
int p=++N_seg; sum[p]=0;
if(L==R) return p;
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
return p;
}
int rt[maxn];
int Update(int pre,int L,int R,int pos,int val){
int p=++N_seg; sum[p]=sum[pre]; ch[p][0]=ch[pre][0]; ch[p][1]=ch[pre][1];
if(L==R) return sum[p]+=val, p;
int mid=(L+R)>>1;
if(pos<=mid) ch[p][0]=Update(ch[pre][0],L,mid,pos,val);
else ch[p][1]=Update(ch[pre][1],mid+1,R,pos,val);
maintain(p); return p;
}
int Query(int p1,int p2,int L,int R,int qL,int qR){
if(R<qL||qR<L) return 0;
if(qL<=L&&R<=qR) return sum[p1]-sum[p2];
int mid=(L+R)>>1;
return Query(ch[p1][0],ch[p2][0],L,mid,qL,qR)+Query(ch[p1][1],ch[p2][1],mid+1,R,qL,qR);
}
int N_sam,sch[maxn][26],Max[maxn],par[maxn],lst;
int newnode(int t){
++N_sam; memset(sch[N_sam],0,sizeof(sch[N_sam]));
Max[N_sam]=t; return N_sam;
}
int pos[maxn],id_sam[maxn];
void Extend(int c,int id){
int p=lst, np=newnode(Max[lst]+1); pos[np]=id; id_sam[id]=np;
while(p&&sch[p][c]==0) sch[p][c]=np, p=par[p];
if(!p) par[np]=1; else{
int q=sch[p][c];
if(Max[q]==Max[p]+1) par[np]=q; else{
int nq=newnode(Max[p]+1);
for(int i=0;i<=25;i++) sch[nq][i]=sch[q][i];
par[nq]=par[q]; par[q]=nq; par[np]=nq;
while(p&&sch[p][c]==q) sch[p][c]=nq, p=par[p];
}
}
lst=np;
}

int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int n,m;
char s[maxn];
int dfn[maxn],out[maxn],idfn[maxn],Tim,anc[maxn][19];
void dfs(int x,int pre){
anc[x][0]=pre; for(int i=1;i<=18;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
dfn[x]=++Tim; idfn[Tim]=x;
for(int j=fir[x];j;j=nxt[j]) dfs(son[j],x);
out[x]=Tim;
}
int getp(int L,int len){
int p=id_sam[L];
for(int i=18;i>=0;i--) if(Max[anc[p][i]]>=len) p=anc[p][i];
return p;
}
int main(){
scanf("%d%d%s",&n,&m,s+1);
newnode(0); lst=1; for(int i=n;i>=1;i--) Extend(s[i]-'a',i);
for(int i=1;i<=N_sam;i++) add(par[i],i);
dfs(1,1);
rt[0]=Build(1,n);
for(int i=1;i<=N_sam;i++){
rt[i]=rt[i-1];
if(pos[idfn[i]]) rt[i]=Update(rt[i],1,n,pos[idfn[i]],1);
}
while(m--){
int L1,R1,L2,R2; scanf("%d%d%d%d",&L1,&R1,&L2,&R2);
int L=1,R=min(R1-L1+1,R2-L2+1),res=0;
while(L<=R){
int mid=(L+R)>>1, p=getp(L2,mid);
//for(int i=L2+mid-1;i>=L2;i--) p=sch[p][s[i]-'a'];
if(Query(rt[out[p]],rt[dfn[p]-1],1,n,L1,R1-mid+1)>0)
res=mid, L=mid+1; else R=mid-1;
}
printf("%d\n",res);
}
return 0;
}