传送门
后缀树的用途，总结起来大概有如下几种: (1). 查找字符串o是否在字符串S中。 方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。 原理：若o在S中，则o必然是S的某个后缀的前缀。 例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie搜索的方法就不难理解了。 (2). 指定字符串T在字符串S中的重复次数。 方案：用S+’$'构造后缀树，搜索T节点下的叶节点数目即为重复次数 原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。 (3). 字符串S中的最长重复子串 方案：原理同2，具体做法就是找到最深的非叶节点。 这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。 为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。 (4). 两个字符串S1，S2的最长公共部分 方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; char s[101000]; int sa[101000], t[101000], t2[101000], c[101000]; int Rank[101000], height[101000]; // 对后缀的第一个字符进行基数排序，m 表示名次的最大值。 //SA[ ]：它的下标就是后缀排名 //c[ ]：用来基数排序。初始值恰好是每种字符出现的次数。 //后来它的作用就跟基数排序密切相关，建议学习基数排序 /* for(int i=0;i<len;i++) m=m>s[i]?m:s[i]; */ inline void build_sa(int m) { int *x = t, *y = t2; int n = strlen(s) + 1; for(int i = 0; i < m; i ++) c[i] = 0; for(int i = 0; i < n; i ++) c[x[i] = s[i]] ++; for(int i = 1; i < m; i ++) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; i --) sa[-- c[x[i]]] = i; for(int k = 1; k <= n; k <<= 1) { int p = 0; for(int i = n - k; i < n; i ++) y[p ++] = i; for(int i = 0; i < n; i ++) if(sa[i] >= k) y[p ++] = sa[i] - k; //x[]的内容就是对应的第一关键字排名 //根据x[]的内容和y[]的下标进行合并，得到新的排名作为sa[]的下标 for(int i = 0; i < m; i ++) c[i] = 0; for(int i = 0; i < n; i ++) c[x[y[i]]] ++; for(int i = 0; i < m; i ++) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; i --) sa[-- c[x[y[i]]]] = y[i]; //按照sa[]的顺序提取出老的x[]，计算新的x[] swap(x, y); p = 1; x[sa[0]] = 0; for(int i = 1; i < n; i ++) { if(y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) x[sa[i]] = p - 1; else x[sa[i]] = p ++; } if(p >= n) break; // 每个后缀的名次已经完全不同，不需要继续倍增 m = p; // 更新名次的最大值。 } for(int i = 1; i < n; i ++) printf("%d ", sa[i] + 1); printf("\n"); return; } inline void getHeight() { int k = 0; int n = strlen(s) + 1; for(int i = 0; i < n; i ++) Rank[sa[i]] = i; for(int i = 0; i < n; i ++) { if(k) k --; // 从 k - 1 开始推 if(!Rank[i]) continue; int j = sa[Rank[i] - 1]; while(s[i + k] == s[j + k] && i + k < n && j + k < n) k ++; height[Rank[i]] = k; } for(int i = 2; i < n; i ++) printf("%d ", height[i]); printf("\n"); } int main() { scanf("%s", s); build_sa(300); getHeight(); return 0; }
例：abaab
那么这样我们就构造出了后缀数组。但本题还有一问，着我们要怎么解决呢？就需要两个辅助数组：rank[]，height[]。rank[i] 用来记录后缀 i 在 SA 数组的位置。height[i] 记录后缀 SA[i] 和 SA[i - 1] 的 LCP 的长度。
首先很容易求出 rank 数组：
for (int i = 0; i < len; i++) rank[SA[i]] = i;如何计算 height 数组呢？最简单的办法，相邻的两个后缀硬求一遍 LCP 时间复杂度 ，有一种更加高效的方法，只需要 时间即可。先令一个辅助数组 h，其中 h[i] = height[rank[j]]。这里有一个神奇的性质：.先来证明一下吧。
设排在后缀(i - 1)前一个的是后缀 k 。后缀(i - 1)和后缀 k 分别删除首字母后得到的是后缀 i 和后缀(k + 1)。因为后缀 k 排在 后缀(i - 1)之前，所以后缀(k + 1) 必定也排在后缀 i 之前，并且它们的 LCP 长度为h[i - 1] + 1。很显然，h[i - 1] - 1 是一系列 h 的最小值。包括排在后缀 i 之前的一个后缀 p 和 后缀 i 的 LCP 长度，即 h[i]。给出代码：
for (int i = 0; i < len; i++) { if (rank[i] == 0) {height[0] = 0; continue;} // 第一个后缀的 LCP 为 0。 if (k) k--; // 从 k - 1 开始推 int j = SA[rank[i] - 1]; while (s[i + k] == s[j + k] && i + k < len && j + k < len) k++; height[rank[i]] = k; }