后缀自动机构造后缀数组。
因为有个SB题洛谷5115，它逼迫我学习后缀数组...(边分树合并是啥？)。
一些定义：sa[i]表示字典序排第i的后缀是从哪里开始的。Rank[i]表示后缀i的排名。height[i]表示排名i和i - 1的后缀的最长公共前缀。
首先我们可以建出后缀树，然后按字典序DFS即可获得sa数组和rank数组。
接下来要求height，使用经典后缀数组的求法即可。
说一下关于后缀数组经典倍增构造方法的一些理解。关于网上流传的那个锯齿形图，其实就是把上一次的两个排名拼接起来进行排序。
height数组的构建也很神奇。按照下标求，可以发现sa[Rank[i]](它自己)和j = sa[Rank[i] - 1]和i + 1的关系：
若i和j的[1, x]这些位相同，那么i + 1和j的[2, x]这些位相同。所以height[Rank[i]]至少有x - 1。
拍过的模板......暂时没找到模板题(板子字符集居然是62...是想卡爆SAM吧)
1 #include <bits/stdc++.h>
2
3 const int N = 200010;
4
5 int n, pw[N], ST[N][20];
6 int tr[N][26], len[N], fail[N], tot = 1, last = 1, ed[N], Lp[N];
7 int tr2[N][26], sa[N], Rank[N], height[N], num;
8 char str[N];
9
10 inline void insert(char c, int id) {
11 int f = c - 'a', p = last, np = ++tot;
12 last = np;
13 ed[np] = 1;
14 Lp[np] = id;
15 len[np] = len[p] + 1;
16 while(p && !tr[p][f]) {
17 tr[p][f] = np;
18 p = fail[p];
19 }
20 if(!p) {
21 fail[np] = 1;
22 }
23 else {
24 int Q = tr[p][f];
25 if(len[Q] == len[p] + 1) {
26 fail[np] = Q;
27 }
28 else {
29 int nQ = ++tot;
30 Lp[nQ] = Lp[Q];
31 len[nQ] = len[p] + 1;
32 fail[nQ] = fail[Q];
33 fail[Q] = fail[np] = nQ;
34 memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
35 while(tr[p][f] == Q) {
36 tr[p][f] = nQ;
37 p = fail[p];
38 }
39 }
40 }
41 return;
42 }
43
44 void DFS(int x) {
45 if(ed[x]) {
46 sa[++num] = Lp[x];
47 Rank[Lp[x]] = num;
48 }
49 for(int i = 0; i < 26; i++) {
50 if(!tr2[x][i]) continue;
51 DFS(tr2[x][i]);
52 }
53 return;
54 }
55
56 inline void getsa() {
57 for(int i = 2; i <= tot; i++) { /// build suffix tree
58 char c = str[Lp[i] + len[fail[i]]];
59 tr2[fail[i]][c - 'a'] = i;
60 }
61 DFS(1); /// DFS suffix tree to get SA and Rank
62 for(int i = 1, j, k = 0; i <= n; i++) { /// get height
63 j = sa[Rank[i] - 1];
64 if(!j) continue;
65 if(k) k--;
66 while(i + k <= n && j + k <= n && str[i + k] == str[j + k]) {
67 k++;
68 }
69 height[Rank[i]] = k;
70 }
71 return;
72 }
73
74 inline void prework() {
75 for(int i = 2; i <= n; i++) pw[i] = pw[i >> 1] + 1;
76 for(int i = 1; i <= n; i++) ST[i][0] = height[i];
77 for(int j = 1; j <= pw[n]; j++) {
78 for(int i = 1; i + (1 << j) - 1 <= n; i++) {
79 ST[i][j] = std::min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
80 }
81 }
82 return;
83 }
84
85 inline getSmall(int l, int r) {
86 if(l > r) std::swap(l, r);
87 l++;
88 int t = pw[r - l + 1];
89 return std::min(ST[l][t], ST[r - (1 << t) + 1][t]);
90 }
91
92 int main() {
93 scanf("%s", str + 1);
94 n = strlen(str + 1);
95 for(int i = n; i >= 1; i--) {
96 insert(str[i], i);
97 }
98 getsa();
99 prework();
100
101 int m;
102 scanf("%d", &m);
103 for(int i = 1; i <= m; i++) {
104 int x, y;
105 scanf("%d%d", &x, &y);
106 if(x == y) {
107 printf("%d ", n - x + 1);
108 }
109 else {
110 int t = getSmall(Rank[x], Rank[y]);
111 printf("%d ", t);
112 }
113 }
114
115 return 0;
116 }
SAM build SA求lcp