---

后缀数组是什么?

如果我要对数组排序的话,按字符串的字典序来排,这个就是后缀数组
以某个位置开始后面整体的后缀串,它在所有开头位置的后缀串中排名第几,把它自己的排名作为一个数组,返回跟它对应的就是rank数组(原始下标按字典序的排名)
后缀数组跟rank数组就是一种转换关系,后缀数组可以在O(N)的时间内转化为rank数组
rank数组可以在O(N)的时间内转化为后缀数组

后缀数组+rank数组可以接解决非常多的字符串问题
还能去做RMQ问题
关键点在于后缀数组怎么样形成最方便

后缀数组的地位

它的地位非常高,很多的问题都是由后缀树或后缀数组实现的
后缀树实现跟后缀数组实现的区别:后缀数组可以替代非常多后缀树的内容,因为后缀树生成是更麻烦的,一个东西我用后缀数组可以代表字符串的一些后缀信息,可以解决很多,字符串的问题

后缀数组的生成

从开头开始往后所有都要
对所有后缀字符串做典序排序
所调的后缀数组它其实代表所有的后缀字符串在排完名之后,从第0名到第7名依次写下来,这就是所调的后缀数组
不会有排名相同的,因为所有后缀串的长度不同

后缀数组可以做到生成复杂度: O(N)
但是有一个前提:初始时,数组里头每一个的值不要太大
如果非常大,下面的方法就不合适了,常数项就会有点大

基数排序

做个升级,有两位数据,每一个数据有两个指标
{56,4}: 56 算一位,不要拆开
对上面数据排序3-7最前
17-79第二
23-34第三位
最后56-4
过两遍桶就可以排好序

如果N个样本,数据的维度不超过3维,而且每个维度的值相对较小(比如1000以内)则N个样本排序的代价可以做到O(N)

概念

后缀数组这个概念并不只局限于字符串

把字符串可以认为是一个数组,每个位数据是这个字符串的ASCII码
你把一个字符串求后缀数组其实就等同于你对一个数组在求后缀数组。
赛中最常用的后缀数组生成算法还有一个倍增算法,复杂度没有DC3好,但是常数项优秀

算法流程

首先字符串长度N
1)有一个f()函数帮我得到S12内部的排名
2)用s12的信息得到s0内部的排名使用基数排序: O(N)
3)把S0跟S12去merge,又利用到s12类的信息,都排出来: O(N)
所以,成败的关键就是第一步,后面两个过程都是O(N)的过程

生成后缀数组

首先,做下标分类
i%3== 0==> 0类下标,代号s0类
i%3== 1==> 1类下标,代号s1类
i%3== 2==> 2类下标,代号s2类

假设有一个非常方便的方法先把S1, S2类的后缀数组排名求出来
我能不能得出所有0类,1类,2类下标的整体排名?
所有3类混在一起的下标排名能不能通过S1, S2类的已经出来的信息,给它都加工出来

怎么使用S1,S2类的信息呢?先看看S12类能不能把S0内部的排名搞定

0开头的a
3开头的a
6开头的c
如果只看一个字符,6的排名是不如0,3的
这个过程可以用基数排序
S0内部的首字母不一样,根据首字母就可以划块了
首字母不一样的块之间的排名,我一定能求出顺序
下面的问题就是0,3开头,这些同样在一个块内部的这些后缀串怎么排名?

0开头的字符是a,后面的是1开头及其后面的所有
3开头的字符也是a,后面的是4开头及其后面的所有
1开头及其后面的所有跟4开头及其后面的所有的总排名我是知道的
虽然第一维数据一样,但是0开头的是干不过3开头的
依然可以基数排序,过一遍决定顺序,O(N),或者说O(s0的大小)还是基数排序,相当于一个对象两位的信息

s0内部排名的加工出来了,s12的内部排名也有了你要想得到整体排名,你只要有merge策略就够了

怎么进行merge呢?
一开始3开头的跟2开头的pk
3开头的上面字符是a,2开头的上面字符也是a,所以要再往下比较,都是a,又比不出来,再往下下面考察5及其后面的整体和4及其后面的整体,这俩排名在s12里有
最多三维信息可以搞定merge只用比三个位置的信息就可以决定3开头跟2开头谁大谁小这都不是基数排序,就三个位置的值比较一下

得到S12类的排名

如何得到S12类的排名呢?我要求这个排名一定要是精确的给我里面不要有重复值

画下划线的就是s12类
怎么决出所有它们的整体排名呢?

先只拿前三维信息做比较
1开头我先不考虑所有,我先只拿前三个字符试一下
1开头前三个字符aab
2开头前三个字符abb
4开头前三个字符bbc
5开头前三个字符bco
7开头前三个字符cca
8开头前三个字符caa
10开头前三个字符aao
11开头前三个字符a00
这个例子展示的是如果我们仅拿3位信息就足以得到严格排名的话,那岂不爽哉一个基数排序,直接精确排名就出来了这个例子是我只拿前3位信息,是直接可以得到精确排名的,又过了一个O(N)的基数排序接下来可以直接去做后面2,3的步骤
现实情况是,有可能只拿前三位信息它排不出严格的排名

拿mississippi这个单词做例子只拿1,2类信息的前3维信息不能得出精确排名

生成一个数组:
把S1类整体放在数组左边,S1类所对应的排名放数组左边
把S2类全放在数组右边,S2类所对应的排名放数组右边

结论:
我把这个数据认为是个字符串数组。
我递归的调用求它后缀数组的排名
求出来了哪个是第一名?1554, 3位置是第一名,对应会原数组中10它是第一名
下面是2开头的21554,对应会原数组中7它是第二名
接下来是321…,是原数组第1位置
接下来是3321…,是原数组第0位置
接下来是4,是原数组第6位置
接下来是54,是原数组第5位置
接下来是554,是原数组第4位置
后缀数组的这个结论求出来以后它可以对应回原来我想求这个东西里面的S12举的排名

解释

一开始有一个比较粗糙的排名,没有得到精确的排名,有两个3,两个5
如果你把这个排名的值当做是字符的话,我这个1不可能在排完字符串之后,排名往后掉,相当于我首字母就是1
首字母如果划分出块了,即便后面怎么摆,也不会让排名乱掉,块与块之间排名不会乱掉,为什么要这么摆?这么摆可以把同一块内部的排名搞定!

看这个两个3
3:1开头及其后面的所有
3:4开头及其后面的所有
分不出来因为我们只拿了前3位信息出来,它们彻底相等,所以区分不出来接下来,你需要什么信息?
3:1234开头及其后面的所有
3:4567开头及其后面的所有
s1类摆在整体左边,s2类摆在整体右边对于同一组内部,这么摆,正好这个结构关系能帮它区分排名

5: 2345开头及其后面的所有
5: 5678开头及其后面的所有
这个例子展示的是,相同的排名信息落在一组里的情况,都落在左组或者都落在右组

相同的信息落在不同组的例子
相同的排名即便是跨组,这么摆,也能搞出区分来
注意一个情况, S1类跟s2类交接的位置比如s1最后一个位置贴的是s2的开头,有可能会产生某些程度的干扰,在实现里是通过补0的方式来免除这个干扰

代码

public class DC3 {

	public int[] sa;

	public int[] rank;

	public int[] height;

	// 构造方法的约定:
	// 数组叫nums，如果你是字符串，请转成整型数组nums
	// 数组中，最小值>=1
	// 如果不满足，处理成满足的，也不会影响使用
	// max, nums里面最大值是多少
	public DC3(int[] nums, int max) {
		sa = sa(nums, max);
		rank = rank();
		height = height(nums);
	}

	private int[] sa(int[] nums, int max) {
		int n = nums.length;
		int[] arr = new int[n + 3];
		for (int i = 0; i < n; i++) {
			arr[i] = nums[i];
		}
		return skew(arr, n, max);
	}

	private int[] skew(int[] nums, int n, int K) {
		int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
		int[] s12 = new int[n02 + 3], sa12 = new int[n02 + 3];
		for (int i = 0, j = 0; i < n + (n0 - n1); ++i) {
			if (0 != i % 3) {
				s12[j++] = i;
			}
		}
		radixPass(nums, s12, sa12, 2, n02, K);
		radixPass(nums, sa12, s12, 1, n02, K);
		radixPass(nums, s12, sa12, 0, n02, K);
		int name = 0, c0 = -1, c1 = -1, c2 = -1;
		for (int i = 0; i < n02; ++i) {
			if (c0 != nums[sa12[i]] || c1 != nums[sa12[i] + 1] || c2 != nums[sa12[i] + 2]) {
				name++;
				c0 = nums[sa12[i]];
				c1 = nums[sa12[i] + 1];
				c2 = nums[sa12[i] + 2];
			}
			if (1 == sa12[i] % 3) {
				s12[sa12[i] / 3] = name;
			} else {
				s12[sa12[i] / 3 + n0] = name;
			}
		}
		if (name < n02) {
			sa12 = skew(s12, n02, name);
			for (int i = 0; i < n02; i++) {
				s12[sa12[i]] = i + 1;
			}
		} else {
			for (int i = 0; i < n02; i++) {
				sa12[s12[i] - 1] = i;
			}
		}
		int[] s0 = new int[n0], sa0 = new int[n0];
		for (int i = 0, j = 0; i < n02; i++) {
			if (sa12[i] < n0) {
				s0[j++] = 3 * sa12[i];
			}
		}
		radixPass(nums, s0, sa0, 0, n0, K);
		int[] sa = new int[n];
		for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
			int i = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2;
			int j = sa0[p];
			if (sa12[t] < n0 ? leq(nums[i], s12[sa12[t] + n0], nums[j], s12[j / 3])
					: leq(nums[i], nums[i + 1], s12[sa12[t] - n0 + 1], nums[j], nums[j + 1], s12[j / 3 + n0])) {
				sa[k] = i;
				t++;
				if (t == n02) {
					for (k++; p < n0; p++, k++) {
						sa[k] = sa0[p];
					}
				}
			} else {
				sa[k] = j;
				p++;
				if (p == n0) {
					for (k++; t < n02; t++, k++) {
						sa[k] = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2;
					}
				}
			}
		}
		return sa;
	}

	private void radixPass(int[] nums, int[] input, int[] output, int offset, int n, int k) {
		int[] cnt = new int[k + 1];
		for (int i = 0; i < n; ++i) {
			cnt[nums[input[i] + offset]]++;
		}
		for (int i = 0, sum = 0; i < cnt.length; ++i) {
			int t = cnt[i];
			cnt[i] = sum;
			sum += t;
		}
		for (int i = 0; i < n; ++i) {
			output[cnt[nums[input[i] + offset]]++] = input[i];
		}
	}

	private boolean leq(int a1, int a2, int b1, int b2) {
		return a1 < b1 || (a1 == b1 && a2 <= b2);
	}

	private boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {
		return a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3));
	}

	private int[] rank() {
		int n = sa.length;
		int[] ans = new int[n];
		for (int i = 0; i < n; i++) {
			ans[sa[i]] = i;
		}
		return ans;
	}

	private int[] height(int[] s) {
		int n = s.length;
		int[] ans = new int[n];
		for (int i = 0, k = 0; i < n; ++i) {
			if (rank[i] != 0) {
				if (k > 0) {
					--k;
				}
				int j = sa[rank[i] - 1];
				while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
					++k;
				}
				ans[rank[i]] = k;
			}
		}
		return ans;
	}

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