【题解】loj#2059 [HEOI/TJOI2016]字符串

给定一个串,每次给出区间 $[a,b]$ 和 $[c,d]$,询问 $[a,b]$ 中的子串与 $s[c…d]$ 的 $lcp$ 最大值。

要求做法 $n~\mathrm{poly}(\log)$,其中 $\deg(\mathrm{poly}(\log))\leq 3$ 。

考虑二分,那么就变成了一个判定性问题,即考虑 $s[c…c+mid-1]$ 在 $[a…b]$ 中是否出现过。那么考虑倍增,对于每个点可以倍增出 $s[1…c+mid-1]$ 的 $endpos$ 所在的那个节点,那么现在就是要求这个 $endpos$ 中是否存在某个元素 $\in$ $[a+mid-1,b]$ 。 那么这个东西就可以插入时维护每个点当前的 $endpos$,之后对当前的 $parent$ 树做一次线段树合并即可。

需要注意的是这种写法的线段树合并可能会炸空间。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

#define to(k) E[k].to
#define next(k) E[k].next

const int N = 500010 ;

int cnt ;
int n, m ;
int Id[N] ;
char t[N] ;
struct EdgE{
int to ;
int next ;
}E[N << 1] ;
int head[N] ;
int dad[N][21] ;

struct Seg{
int size ;
int lc[N * 15] ;
int rc[N * 15] ;
int rt[N * 15] ;
int sum[N * 15] ;
void Ins(int &rt, int l, int r, int v){
if (!rt) rt = ++ size ;
int mid = (l + r) >> 1 ;
sum[rt] ++ ; if (l == r) return ;
if (v <= mid) Ins(lc[rt], l, mid, v) ;
else Ins(rc[rt], mid + 1, r, v) ;
}
int query(int rt, int l, int r, int ql, int qr){
if (ql <= l && r <= qr) return sum[rt] ;
int mid = (l + r) >> 1 ; int res = 0 ;
if (ql <= mid) res += query(lc[rt], l, mid, ql, qr) ;
if (qr > mid) res += query(rc[rt], mid + 1, r, ql, qr) ;
return res ;
}
int merge(int x, int y, int l, int r){
int p = ++ size ;
if (!x) return y ;
if (!y) return x ;
if (l == r) return p ;
int mid = (l + r) >> 1 ;
sum[p] = sum[x] + sum[y] ;
lc[p] = merge(lc[x], lc[y], l, mid) ;
rc[p] = merge(rc[x], rc[y], mid + 1, r) ;
return p ;
}
}T ;
void add(int u, int v){
to(++ cnt) = v ;
next(cnt) = head[u] ;
head[u] = cnt ;
}
void dfs(int x){
for (int k = 1 ; k <= 20 ; ++ k)
dad[x][k] = dad[dad[x][k - 1]][k - 1] ;
for (int k = head[x] ; k ; k = next(k)){
dad[to(k)][0] = x, dfs(to(k)) ;
T.rt[x] = T.merge(T.rt[x], T.rt[to(k)], 1, n) ;
}
}
struct SAM{
int fa[N] ;
int len[N] ;
int last, size ;
int trans[N][26] ;
void Init(){
last = ++ size ;
}
int Ins(int x){
int np = ++ size ;
int p = last, q, nq ;
len[last = np] = len[p] + 1 ;
while (p && !trans[p][x])
trans[p][x] = np, p = fa[p] ;
if (!p)
return fa[np] = 1, last ;
q = trans[p][x] ;
if (len[q] == len[p] + 1)
return fa[np] = q, last ;
nq = ++ size ;
fa[nq] = fa[q] ;
fa[q] = fa[np] = nq ;
len[nq] = len[p] + 1 ;
memcpy(trans[nq], trans[q], 104) ;
while (n && trans[p][x] == q)
trans[p][x] = nq, p = fa[p] ;
return last ;
}
void Add(){
for (int i = 2 ; i <= size ; ++ i) add(fa[i], i) ;
}
}S ;
int main(){
// freopen("str5.in", "r", stdin) ;
cin >> n >> m ;
int a, b, c, d ;
cin >> (t + 1), S.Init() ;
for (int i = 1 ; i <= n ; ++ i){
Id[i] = S.Ins(t[i] - 'a') ;
T.Ins(T.rt[Id[i]], 1, n, i) ;
}
S.Add() ; dfs(1) ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d%d%d", &a, &b, &c, &d) ;
int l = 1, r = min(b - a + 1, d - c + 1), mid, ans = 0 ;
//cout << l << r << endl ;
while (l <= r){
mid = (l + r) >> 1 ;
int x = Id[c + mid - 1] ;
// cout << mid << endl ;
for (int j = 20 ; j >= 0 ; -- j)
if (dad[x][j] && S.len[dad[x][j]] >= mid)
x = dad[x][j] ;
// cout << x << endl ;
if (T.query(T.rt[x], 1, n, a + mid - 1, b))
ans = mid, l = mid + 1 ; else r = mid - 1 ;
}
printf("%d\n", ans) ;
}
return 0 ;
}