后缀数组的应用理解

前言

字符串一直是短板，之前遇到字符串都是直接跳过，也曾经尝试多次去学习后缀数组，每次都是扫完全文但是不懂。最近终于可以自己用后缀数组去过题目了，简单记录下理解。

构建

构建部分主要是倍增的思想，和一些贪心？结论，具体可以参见OI-wiki,这里就不再赘述。

理解

假设你需要在一个数组中匹配是否出现一个数字，以及这个数字出现了几次，可以采用哈希的方法，也可以采用排序数组的方法。同样，对于一堆字符串，你也可以通过哈希，或者排序数组的方法来解决这类问题。
如果这一堆字符串是一个字符串的所有子串，直接存储$O(n)$个子串需要$O(n^3)$的时空复杂度，即使采用哈希也只能降到$(O(n^2))$。后缀数组就是用下标i来代替整个后缀S[i:]，使得存储只需要$O(n)$复杂度，构建只需要少于$O(n\log(n))$复杂度。但是只存后缀怎么来解决对所有子串的操作呢？
假设我们有一个字符串aabaaaab，他的后缀分别是：

aabaaaab
abaaaab
baaaab
aaaab
aaab
aab
ab
b

对它们进行排序：

aaaab
aaab
aab
aabaaaab
ab
abaaaab
b
baaaab

任何一个子串一定是某个后缀的前缀，由于字符串排序实质就是前缀去做比较，所以后缀的排序其实跟所有子串的排序有关，如下：

aaaab: a < aa < aaa < aaaa < aaaab
aaab: a < aa < aaa < aaab
aab: a < aa < aab
aabaaaab: a < aa < aab < aaba < aabaa < aabaaa < aabaaaa < aabaaaab
ab: a < ab
abaaaab: a < ab < aba < abaa < abaaa < abaaaa < abaaaab
b: b
baaaab: b < ba < baa < baaa < baaaa < baaaab

但是可以看到，后缀的排序并不完全等于子串的排序，如果我们想知道子串的排序，应该怎么做呢？可以发现对于前3项：

aaaab: a < aa < aaa < aaaa < aaaab
aaab: a < aa < aaa < aaab
aab: a < aa < aab

a和aa这两个子串同时出现在了前3项里面，aaa出现在了前2项里面，与aaa同一列的第3项是aab，aab>aaa。同样可以发现，相邻两个后缀之间有一部分前缀是完全相同的，我们认为这些相同的子串实际在排序中的位置是第一次出现的位置（例如aa应该是第1行第2列），那么我们就得到了所有子串的排序所需要的全部信息。这就是后缀数组的本质：得到所有子串的排序信息。
为了高效处理相邻的两个后缀之间的相同前缀，我们得到了height数组，height[i]=lcp(sa[i-1]. sa[1])，即height数组存了每个后缀和他之前后缀的最长公共前缀。这个height名字取得也很形象，拿上面3项来说：

b
a b
a a b
a a a
a a a
0 3 2

我们看到height[2]=3,代表了第2个后缀aaab的前缀a和aa和aaa前一项也存在, height[3]=2代表了a和aa在前一个后缀中也存在。这和高度有啥关系呢？在这个例子里面，除去第一项的高度（因为它和空串在做对比）别的都是>=2的，意味着aa及aa的所有前缀存在于所有的后缀中。而对于height[2]=3但是height[3]=2，高度降低了1，意味着aaa这个前缀，在第3个子串之前消失了。
可以发现，所有height记录的都是出现超过1次的子串信息，将这个数组列成直方图：

 +   +
 + + +   +
 + + + + +   +

我们以行视角来看，最底下一行连续出现了5次，然后断开，然后又出现了1次。左边的连续5个代表了a这个子串出现了5+1次，右边的1个代表了b这个子串出现了1次。我们查看原串aabaaaab，的确如此，a出现了6次，b出现了2次。同样我们可以看到高度为2的最开始出现了3次，代表aa这个子串出现了4次。所以**height数组存储了所有出现超过1次的子串的频数信息**。
这里举个应用的例子，我想知道一个字符串里面不同的子串有多少个。每个height[i]=x的代表有x个子串（即S[i:][:x]的所有前缀）在之前已经存在过了，所以我们可以用所有的子串数量n*(n+1)/2减去所有height的和即可得到。
那如果我想知道所有仅出现过一次的不同子串有多少个要怎么做呢？对于S[i:]这个后缀，它和之前之后后缀的LCP，都是不满足的，超过2个LCP的全部满足。所以S[i:]这个后缀的所有只出现过一次的不同子串是len(S[i:])-max(height[i], height[i+1])。全部加起来即可。
如果是想知道所有出现次数为x的子串有多少个要怎么做呢，回到直方图，一行一行来看，第i行连续的长度就是长度为i的子串的出现次数-1。这个就是直方图里面的面积统计，可以用单调栈来做，也可以用分治法来做。我觉得这个单调栈好难写，所以一直都是ST表然后用分治法去做。这里我们可以看出来height数组的名字就是说它可以转为直方图里面的高度，而height数组存储了所有超过1次的子串的频数信息。对于所有子串去统计一些跟子串长度/数量有关系的题目，大多就是这样去做，转化成直方图里面的处理。