K-th occurrence （后缀自动机上合并权值线段树+树上倍增）
You are given a string $S$ consisting of only lowercase english letters and some queries.
For each query $(l,r,k)$, please output the starting position of the k-th occurence of the substring $S_lS_{l+1}\cdots S_r$ in $S$.
Input
The first line contains an integer $T(1≤T≤20)$, denoting the number of test cases.
The first line of each test case contains two integer $N(1≤N≤10^5),Q(1≤Q≤10^5)$, denoting the length of $S$ and the number of queries.
The second line of each test case contains a string $S(|S|=N)$ consisting of only lowercase english letters. Then $Q$ lines follow, each line contains three integer $l,r(1≤l≤r≤N)$ and $k(1≤k≤N)$, denoting a query. There are at most 5 testcases which $N$ is greater than $10^3$.
Output
For each query, output the starting position of the k-th occurence of the given substring. If such position don’t exists, output -1 instead.
Sample Input
2
12 6
aaabaabaaaab
3 3 4
2 3 2
7 8 3
3 4 2
1 4 2
8 12 1
1 1
a
1 1 1
Sample Output
5
2
-1
6
9
8
1
题目大意：
给出一个字符串$S(|S|\leq 10^5)$，然后有$Q(Q\leq 10^5)$个询问，每个询问包含三个正整数$L,R,K(1\leq L\leq R\leq |S|,1\leq K\leq |S|)$，代表询问$S_LS_{L+1}\cdots S_R$这个$S$的子串在$S$中第$K$次出现的位置是哪里，如果$S$的这个子串出现次数小于$K$，就输出-1。
题目总览：
首先，这道题要求S的某个子串的出现位置，毫无疑问就是求这个子串在后缀自动机上的endpos。而endpos是对应于自动机上的状态节点的，因此我们首先要找到S所求的子串对应的状态节点。接着，我们要求所有状态节点的endpos集合，并支持查询第$K$小，这样就能建立子串-状态节点-endpos集合的关系，从而能求出相应子串的第$K$次出现的位置了。
求子串对应的状态节点：
首先，我们定义$u[i]$为$S$从1到$i$的子串对应于自动机上的状态节点编号。在构造自动机的过程中，我们是从自动机的初始状态出发的，因此u数组可以边构造边更新。1
2
3
4
5
6for (int i = 0; i < N; ++i) {
//自动机插入一个字符
sam.insert(S[i] - 'a');
//等于该字符插入时的状态，编号从1开始
u[i + 1] = sam.cur;
}
现在，我们知道了从1开始的所有子串对应的状态节点了，那么怎样求从l到r对应的状态节点呢？显然l到r是1到r的后缀，那么根据后缀自动机的性质，l到r要么是1到r对应的节点，要么是其后缀连接树上的父节点。设p为l到r的对应状态，那么p满足$maxlen(link(p))<(r-l+1)\leq maxlen(p)$，即1到r的满足$(r-l+1)\leq maxlen(p)$的第一个父节点（或它本身）。这样的话，我们只要根据后缀连接边来建一棵树，然后不断往父节点跳知道满足条件即可。但是，这样的话时间复杂度就是$O(|S|)$，而对应于$Q$个询问显然会超时。不过对于树上跳，我们可以采用树上倍增的方式进行优化。
$Depth[i]$表示第i个节点的深度
$Father[i][j]$表示第i个节点的第$2^j$级祖先的编号
$Log[i]$表示$log_2i$向上取整
$EndPosToTree[i]$表示状态节点i对应于线段树上相应的根的编号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
58class {
int Depth[2 * MAXN];
int Father[2 * MAXN][22];
int Log2[2 * MAXN];
//树上DFS求Depth和Father数组
void DFS(int root, int father = 0) {
Depth[root] = Depth[father] + 1;
Father[root][0] = father;
//一个节点的2^i祖先等于他的2^i-1祖先的2^i-1祖先
for (int i = 1; i <= Log2[Depth[root]]; ++i) {
Father[root][i] = Father[Father[root][i - 1]][i - 1];
}
for (const auto& Next : Edges[root]) {
if (Next != father) {
DFS(Next, root);
}
}
}
public:
//记录树结构
vector<int> Edges[2 * MAXN];
//初始化log2，优化时间
void InitLog2() {
for (int i = 1; i < 2 * MAXN; ++i) {
Log2[i] = Log2[i - 1] + (1 << Log2[i - 1] == i);
}
}
void AddEdge(const int& x, const int& y) {
this->Edges[x].emplace_back(y);
this->Edges[y].emplace_back(x);
}
//树上倍增
int getAncestor(int Point, bool (*Condition)(const int&))const {
//从最高级别的祖先起跳
for (int k = Log2[Depth[Point]]; k >= 0; --k) {
//满足条件就跳
if (Condition(Father[Point][k])) {
Point = Father[Point][k];
}
}
return Point;
}
void Clear() {
memset(Depth, 0x0, sizeof(Depth));
memset(Father, 0x0, sizeof(Father));
for (int i = 0; i <= 2 * N + 1; ++i) {
Edges[i].clear();
}
}
void Init() {
Clear();
for (int i = 1; i < sam.size; ++i) {
const int& Link = sam.node[i].link;
MultiplyOnTree.AddEdge(i, Link);
}
DFS(0);
}
}MultiplyOnTree;
求状态节点的endpos集合并维护第k小：
根据后缀自动机的性质，一个节点的endpos集合等于其所有后缀连接树上子节点的endpos集合的交集，即父节点是子节点的后缀。而叶节点的endpos集合就是自动机构造时插入的字符的位置，大小为1。但是在寻找第k小时，如果$O(N)$遍历，对于$Q$个询问显然后超时。不过我们可以用合并权值线段树的方法来维护第k小。
$Tree[i]$表示线段树上的i个节点所管辖的范围有多少个数
$LeftSon[i],RightSon[i]$表示第i个节点的左右儿子的编号
$Radix,Order$用于计数排序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
98class SegmentTree {
friend class SAM;
int Tot;
int
Tree[50 * MAXN],
LeftSon[50 * MAXN],
RightSon[50 * MAXN],
Radix[MAXN],
Order[2 * MAXN];
public:
void Clear() {
Tot = 0;
memset(Tree, 0x0, sizeof(Tree));
memset(Radix, 0x0, sizeof(Radix));
}
SegmentTree() = default;
//合并两棵权值线段树
int Merge(int Left, int Right) {
if (!Left || !Right) {
return Left | Right;
}
int NewRoot = ++Tot;
LeftSon[NewRoot] = Merge(LeftSon[Left], LeftSon[Right]);
RightSon[NewRoot] = Merge(RightSon[Left], RightSon[Right]);
this->Tree[NewRoot] = this->Tree[LeftSon[NewRoot]] + this->Tree[RightSon[NewRoot]];
return NewRoot;
}
//单点更新
void Update(int Loc, int& root, int Left = 1, int Right = N) {
//如果是新加入的根节点，就为它分配一个新节点编号
if (!root) {
root = ++Tot;
Tree[root] = LeftSon[root] = RightSon[root] = 0;
}
//找到了对应的位置，数量++
if (Left == Right) {
++Tree[root];
return;
}
int&& mid = (Right + Left) >> 1;
if (Loc <= mid) {
Update(Loc, LeftSon[root], Left, mid);
}
else {
Update(Loc, RightSon[root], mid + 1, Right);
}
//UpGrade
this->Tree[root] = this->Tree[LeftSon[root]] + this->Tree[RightSon[root]];
}
//寻找第k小
int getK_th(int Left, int Right, int K, int root) {
if (Left == Right) {
return Left;
}
int&& mid = (Left + Right) >> 1;
const int
& LeftSonValue = this->Tree[this->LeftSon[root]],
& RightSonValue = this->Tree[this->RightSon[root]];
//如果左边的数量大于k，说明在左边
if (LeftSonValue >= K) {
return getK_th(Left, mid, K, LeftSon[root]);
}
//如果右边的数量大于k-左边的数量，说明在右边
else if (RightSonValue >= K - LeftSonValue) {
return getK_th(mid + 1, Right, K - LeftSonValue, RightSon[root]);
}
//反则就不存在
else {
return -1;
}
}
int getAns(int K, int P, int Left = 1, int Right = N) {
int&& Ans = this->getK_th(Left, Right, K, EndPosToTree[P]);
//子串右端位置转左端位置
return (Ans == -1 ? -1 : Ans - (R - L));
}
//计数排序
void CountingSort() {
for (int i = 0; i < sam.size; ++i) {
++Radix[sam.node[i].len];
}
for (int i = 1; i <= sam.node[sam.cur].len; ++i) {
Radix[i] += Radix[i - 1];
}
for (int i = 0; i < sam.size; ++i) {
Order[Radix[sam.node[i].len]--] = i;
}
}
void Init() {
CountingSort();
//按maxlen（p）从小到大更新，就能保父节点后于子节点更新
for (int i = sam.size; i > 1; --i) {
const int& Son = Order[i];
const int& Father = sam.node[Son].link;
EndPosToTree[Father] = SegmentTrees.Merge(EndPosToTree[Father], EndPosToTree[Son]);
}
}
}SegmentTrees;
AC代码：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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
using namespace std;
const int MAXN = 1e5 + 5;
int N, L, R, K, Q;
char S[MAXN];
int u[MAXN];//1...r
int StateToTree[2 * MAXN];
struct SAM {
int size, last, cur;
struct Node {
int len = 0, link = 0;
int next[26];
void clear() {
len = link = 0;
memset(next, 0, sizeof(next));
}
} node[MAXN * 2];
void init() {
for (int i = 0; i < size; i++) {
node[i].clear();
}
node[0].link = -1;
size = 1;
last = 0;
}
void insert(char x) {
int ch = x;
cur = size++;
node[cur].len = node[last].len + 1;
int p = last;
while (p != -1 && !node[p].next[ch]) {
node[p].next[ch] = cur;
p = node[p].link;
}
if (p == -1) {
node[cur].link = 0;
}
else {
int q = node[p].next[ch];
if (node[p].len + 1 == node[q].len) {
node[cur].link = q;
}
else {
int clone = size++;
StateToTree[clone] = 0;
node[clone] = node[q];
node[clone].len = node[p].len + 1;
while (p != -1 && node[p].next[ch] == q) {
node[p].next[ch] = clone;
p = node[p].link;
}
node[q].link = node[cur].link = clone;
}
}
last = cur;
}
}sam;
class {
int Depth[2 * MAXN];
int Father[2 * MAXN][22];
int Log2[2 * MAXN];
void DFS(int root, int father = 0) {
Depth[root] = Depth[father] + 1;
Father[root][0] = father;
for (int i = 1; i <= Log2[Depth[root]]; ++i) {
Father[root][i] = Father[Father[root][i - 1]][i - 1];
}
for (const auto& Next : Edges[root]) {
if (Next != father) {
DFS(Next, root);
}
}
}
public:
vector<int> Edges[2 * MAXN];
void InitLog2() {
for (int i = 1; i < 2 * MAXN; ++i) {
Log2[i] = Log2[i - 1] + (1 << Log2[i - 1] == i);
}
}
void AddEdge(const int& x, const int& y) {
this->Edges[x].emplace_back(y);
this->Edges[y].emplace_back(x);
}
void Start() {
DFS(0);
}
int getAncestor(int Point, bool (*Condition)(const int&))const {
for (int k = Log2[Depth[Point]]; k >= 0; --k) {
if (Condition(Father[Point][k])) {
Point = Father[Point][k];
}
}
return Point;
}
void Clear() {
memset(Depth, 0x0, sizeof(Depth));
memset(Father, 0x0, sizeof(Father));
for (int i = 0; i <= 2 * N + 1; ++i) {
Edges[i].clear();
}
}
void Init() {
Clear();
for (int i = 1; i < sam.size; ++i) {
const int& Link = sam.node[i].link;
MultiplyOnTree.AddEdge(i, Link);
}
Start();
}
}MultiplyOnTree;
class SegmentTree {
friend class SAM;
int Tot;
int
Tree[50 * MAXN],
LeftSon[50 * MAXN],
RightSon[50 * MAXN],
Radix[MAXN],
Order[2 * MAXN];
public:
void Clear() {
Tot = 0;
memset(Tree, 0x0, sizeof(Tree));
memset(Radix, 0x0, sizeof(Radix));
}
SegmentTree() = default;
int Merge(int Left, int Right) {
if (!Left || !Right) {
return Left | Right;
}
int NewRoot = ++Tot;
LeftSon[NewRoot] = Merge(LeftSon[Left], LeftSon[Right]);
RightSon[NewRoot] = Merge(RightSon[Left], RightSon[Right]);
this->Tree[NewRoot] = this->Tree[LeftSon[NewRoot]] + this->Tree[RightSon[NewRoot]];
return NewRoot;
}
void Update(int Loc, int& root, int Left = 1, int Right = N) {
if (!root) {
root = ++Tot;
Tree[root] = LeftSon[root] = RightSon[root] = 0;
}
if (Left == Right) {
++Tree[root];
return;
}
int&& mid = (Right + Left) >> 1;
if (Loc <= mid) {
Update(Loc, LeftSon[root], Left, mid);
}
else {
Update(Loc, RightSon[root], mid + 1, Right);
}
this->Tree[root] = this->Tree[LeftSon[root]] + this->Tree[RightSon[root]];
}
int getK_th(int Left, int Right, int K, int root) {
if (Left == Right) {
return Left;
}
int&& mid = (Left + Right) >> 1;
const int
& LeftSonValue = this->Tree[this->LeftSon[root]],
& RightSonValue = this->Tree[this->RightSon[root]];
if (LeftSonValue >= K) {
return getK_th(Left, mid, K, LeftSon[root]);
}
else if (RightSonValue >= K - LeftSonValue) {
return getK_th(mid + 1, Right, K - LeftSonValue, RightSon[root]);
}
else {
return -1;
}
}
int getAns(int K, int P, int Left = 1, int Right = N) {
int&& Ans = this->getK_th(Left, Right, K, StateToTree[P]);
return (Ans == -1 ? -1 : Ans - (R - L));
}
void CountingSort() {
for (int i = 0; i < sam.size; ++i) {
++Radix[sam.node[i].len];
}
for (int i = 1; i <= sam.node[sam.cur].len; ++i) {
Radix[i] += Radix[i - 1];
}
for (int i = 0; i < sam.size; ++i) {
Order[Radix[sam.node[i].len]--] = i;
}
}
void Init() {
CountingSort();
for (int i = sam.size; i > 1; --i) {
const int& Son = Order[i];
const int& Father = sam.node[Son].link;
StateToTree[Father] = SegmentTrees.Merge(StateToTree[Father], StateToTree[Son]);
}
}
}SegmentTrees;
void Init() {
sam.init();
SegmentTrees.Clear();
}
void Input() {
scanf("%d%d", &N, &Q);
scanf("%s", S);
Init();
for (int i = 0; i < N; ++i) {
sam.insert(S[i] - 'a');
StateToTree[sam.cur] = 0;
SegmentTrees.Update(i + 1, StateToTree[sam.cur]);
u[i + 1] = sam.cur;
}
}
bool Condition(const int& Point) {
return R - L + 1 <= sam.node[Point].len;
}
int main() {
int T;
scanf("%d", &T);
MultiplyOnTree.InitLog2();
while (T--) {
Input();
MultiplyOnTree.Init();
SegmentTrees.Init();
while (Q--) {
scanf("%d%d%d", &L, &R, &K);
const int&& P = MultiplyOnTree.getAncestor(u[R], Condition);
printf("%d\n", SegmentTrees.getAns(K, P));
}
}
return 0;
}
