数据结构之后缀树

一、理解：

1、后缀树，举例说明：

eg: 利用字符串prop建立后缀树。
暴力地说，可以三步建树。
第一步，得到prop的所有后缀：
B[0] = “”
B[1] = “p”，第四个后缀
B[2] = “op”，第三个后缀
B[3] = “rop”，第二个后缀
B[4] = “prop”，第一个后缀
以上五个，都是它的后缀
第二步，用这五个后缀建立trie树。
第三步，压缩：
如果一段树枝既没有分支，又没有哪一条后缀结束，它就要压缩成一个点；
如果一段树枝没有分支，但是有一条后缀在其中结束了，就先为结束点建立一个空节点，再让剩余部分压缩成点。
这样就不会把后缀也压缩掉了，压缩完就是后缀树，长这样：

建议自己先画一遍

2.后缀树与后缀数组（SA）和后缀自动机（SAM）：虽然三者的前缀相同，但后缀的进化程度倍增，不是同纲。

例如后缀数组：
市面上常见两种写法：倍增（O(nlogn)）和DC3（O(n)）。
DC3，又称skew，y总说它的常数比倍增大，而且难写，所以一般用倍增。
倍增写法把字符串的所有后缀按字典序排序（基数排序），排完序得到的就是后缀数组SA：
SA[i]：排名第i位的是第几个后缀（不考虑空后缀）
而一般会用到的数组height：
height[i]：sa[i]和sa[i-1]的最长公共前缀
是后缀数组扩展得来的。
并且通过扩展功能，后缀数组可以逐渐向后缀树转化。

3.为什么没见人用后缀树：后缀树功能完整，构造算法也逐渐优化了。

后缀树魔法：
1.查找字符串S1是否在字符串S2中
2.计算字符串a在字符串S中的重复次数
3.查找字符串S中的最长重复子串
4.查找字符串S1和S2的最长公共子序列（LCP）
5.广义后缀树：处理多个字符串的后缀，分别加标记就行
但是功能完整就表示效率不是最优，而且它难写。

后缀树的确炫酷，但是我劝大家学后缀数组。
建树的算法学一个通宵午不一定能学会一个，而学两个小时的后缀数组，就能求LCP

二、前置技能：

基数排序O(n+k)：

eg：数组A={9, 7, 5, 5, 4}
第一步，计数：
B[4]=1
B[5]=3
B[7]=4
B[9]=5
B[i]表示小于等于i的数的个数
第二步，遍历数组A并排序：
A[0]=9，排序为B[9]=5，B[9]–
A[1]=7，排序为B[7]=4，B[7]–
A[2]=5，排序为B[5]=3，B[5]–
A[3]=5，排序为B[5]=2，B[5]–
A[4]=4，排序为B[4]=1，B[4]—
注意：A[2]的5排序为3，A[3]的5排序为2。
如果第二步遍历时从后往前遍历，就变成A[2]的5排序为2，A[3]的5排序为3。

lcp的两个性质：

1.lcp[i, j]表示排名第i位的后缀和排名第j位的后缀的lcp。
那么显然有lcp[i, j] = min(lcp[i, k], lcp[k, j])，i≤k≤j。
所以lcp[i, j] = min(lcp[i, i+1], lcp[i+1, i+2], …, lcp[j-1, j])。
2.height[i] = lcp[i-1,i]
定义h[i] = height[ rk[i] ]，即第i个后缀的height，即第i个后缀和排名比它小一位的后缀的lcp。
那么有h[i]≥h[i-1]-1。

三、后缀数组

输入一个字符串s，求sa数组和height数组。

先上代码：

#include<bits/stdc++.h>//acwing2715
using namespace std;
const int N=1000010;
int n,m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];

void get_sa(){
	//第一轮排序，只按第一个字母排
    for(int i=1; i<=n; i++) x[i]=s[i], c[x[i]]++;	//计数，并预处理x[i]
    for(int i=2; i<=m; i++) c[i]+=c[i-1];	//计数结果存进c[i]
    for(int i=n; i; i--) sa[ c[x[i]]-- ] = i;	//排序，排完序记得--
	
	//从第二轮往后, 共logn轮, 按长度为k的第一、第二关键字排序
    for(int k=1; k<=n; k<<=1) {
        int num=0;
        
        //先按第二关键字排序
        for(int i=n-k+1; i<=n; i++) y[++num] = i;	//保证第二关键字为空的一定最小
        for(int i=1; i<=n; i++)	//遍历所有后缀
            if(sa[i]>k)	//前k个后缀没有第二关键字
                y[++num] = sa[i] - k;	//排序, sa数组是上一轮排序的结果
		
		//再按第一关键字排序
        for(int i=1; i<=m; i++) c[i]=0;	//c[i]要预处理为0
        for(int i=1; i<=n; i++) c[ x[i] ]++;
        for(int i=2; i<=m; i++) c[i]+=c[i-1];
        for(int i=n; i; i--) sa[ c[ x[ y[i] ] ]-- ] =y[i], y[i]=0;
        //倒序遍历, 相对稳定, 顺便清空y数组
		
		//排序结束后, 更新离散化数组x
        swap(x, y);	//把当前x暂时存进y里
        x[ sa[1] ]=1, num=1;	//排名最小的后缀离散化成1
        for(int i=2; i<=n; i++) {
        	//离散化, 相同数字不变, 不同就++
            x[sa[i]] = ( y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ) ? num : ++num;
        }
        
        if(num==n) break;	//num==n, 即本轮排序已经能区分出所有后缀
        m=num;
    }
}

void get_height(){
    for(int i=1; i<=n; i++) rk[sa[i]]=i;	//排名第i位的后缀的排名是i
    for(int i=1, k=0; i<=n; i++) {
        if(rk[i]==1) continue;	//height[1]=0
        if(k>0) k--;	//去掉前面已经比较的一个字符
        int j=sa[rk[i]-1];	//j表示排名第i位的后缀前面的后缀
        while(i+k<=n && s[i+k]==s[j+k]) k++;	//从k位置开始比较
        height[rk[i]]=k;	//h[i]=k
    }
}

int main(){
    scanf("%s", s+1);
    n=strlen(s+1), m='z';
    get_sa();
    get_height();

    for(int i=1; i<=n; i++) printf("%d ", sa[i]);
    puts("");
    for(int i=1; i<=n; i++) printf("%d ", height[i]);
    puts("");
    return 0;
}
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

求sa：

后缀的第一个字母：遍历字符串s，则s[i]为第i个后缀的第一个字母。
【第一轮排序，只按每个后缀的第一个字母排】：
第一轮排序里出现的x[i]就是s[i]的ascii码。当然，x[i]也是排序结果离散化后的数字。
1.遍历字符串，c数组统计字母出现次数。
2.再遍历c[i]，累加，就可求出小于等于第i个字母的个数。
3.倒序遍历s[i]，排序结果暂存于sa[i]。
【后面logn轮排序，按前k个字母和前k+1到2k个字母排序】：
由于上一轮的离散化，本轮的前k个字母和前k+1到2k个字母变成数字。
遍历logn轮：
（先按第一关键字排序）：
由于字符串的最后k个后缀的长度不足k+1，它们的第二关键字均为空，所以按第二关键字来排，它们一定是最小的。所以：
1.先遍历一遍最后k个后缀，给它们赋个值。
第i个后缀的前k+1到2k个字母，就是第i+k个后缀的前k个字母。所以：
2.遍历所有后缀，把第i+k个后缀的第二关键字，当成第i个后缀的第一关键字。此处直接用上一轮的排序结果sa[i]，-k后就是第i个后缀。//需要理解的第一点
（再按第二关键字排序）：
3.与第一轮思路一样，只是c数组需要清空。
（排序结束后的离散化）：
4.按照排好的顺序从1依次开始离散化。
当离散化的最大值等于n，即能区分所有后缀时，就可以停止循环。

求height：

先处理出rk数组。
再遍历所有后缀，处理出height，height[1]=0跳过。
因为h[i]≥h[i-1]-1，所以在求h[i]时，可以从第k个字符开始枚举比较。//需要理解的第二点
如果第k个字符相同，且不为空，则k++比较下一个字符；
否则k不变，然后等到下一轮循环时，k–，就可以保证比较的位置不变。
所有循环中，k最多从0减到-n，再到n，总共2n，所以时间复杂度O(n)。