后缀数组的一些应用和题目，这里所有的时间复杂度均针对 SA-IS 算法。
「SPOJ694」Distinct Substrings
链接
题解
题意就是给定一个字符串，求该字符串含有的本质不同的子串数量。
由于每个子串都是某个后缀的前缀，我们可以统计每个后缀的数量，而排名第 $i$ 的后缀与排名第 $i - 1$ 的后缀有 $height[i]$ 个相同的前缀，所以从答案中减去这些。
即答案为
$$\sum_{i = 1}^{len(s)}(len(suffix(i - 1)) - height[i])$$
时间复杂度为 $O(n)$。
代码
1 | /******************************************************************************* |
「SDOI2016」生成魔咒
链接
题解
题意就是每次加一个字符，求本质不同的子串的个数。
我们可以离线，先把所有数字离散化，然后把字符串倒过来建后缀数组，往最后加字符变成了添加一个后缀。
我们知道，在求出 $SA$ 之后，一个字符串的本质不同的子串的个数等于 $\frac {n(n + 1)} {2} - \sum height[i]$，每插入一个后缀，在所有已经插入的后缀中，找到它的前驱和后继。又因为两个后缀的 $LCP$，即重复计数的子串个数等于 $height$ 上的区间最小值。
时间复杂度 $O(n \log n)$
代码
1 | /******************************************************************************* |
「AHOI2013」差异
链接
题解
因为每个后缀均被枚举了 $n - 1$ 次，所以
$$\sum_{1 \leq i < j \leq n}len(T_i) + len(T_j) = (n - 1) \times \frac {n(n + 1)} {2}$$而两个后缀的 $lcp(T_i, T_j)$ 的长度应为 $min \text{ } height[k], k \in [rank[i] + 1, rank[j]]$，则：
$$\sum_{1 \leq i < j \leq n}len(lcp(T_i, T_j)) = \sum_{1 \leq i < j \leq n}min \text{ } height[k], k \in [i + 1, j]$$即所有区间的 $height$ 的最小值之和，我们可以枚举区间的结尾 $i$，在这之前比 $height[i]$ 大的值都不不会对答案产生影响，考虑使用单调栈维护，当考虑到 $i$ 对答案的贡献时，记在 $i$ 之前第一个满足 $height[j] < height[i]$ 的 $j$，区间开头在 $[j + 1, i]$ 内的区间最小值均为 $height[i]$，即对答案的贡献为 $(i - j) \times height[i]$，从头枚举一遍即可。
时间复杂度 $O(n)$，目前 BZOJ rk1 black SA 不知道比 SAM 快到哪里去了
代码
1 | /******************************************************************************* |
「POJ2774」Long Long Message
链接
题解
题意:给定两个字符串求最长公共子串。
这是后缀数组的经典题，用后缀自动机也同样可做。
把两个串插分隔符连接起来建后缀数组，最长公共子串即转化为了最长公共前缀，我们枚举 $height$ 数组，如果相邻排名的两个后缀分别为 $S_1, S_2$ 的子串，我们就用这个 $height$ 更新答案，由于不相邻的后缀的最长公共前缀只会更小，所以我们这样扫一遍取最大即为答案。
时间复杂度 $O(n)$
代码
1 | /******************************************************************************* |
「POJ1743」Musical Theme
链接
题解
此题就是求不可重叠最长重复子串。
若可重叠则答案就是 $height$ 的最大值，但这里要求不可重叠。
考虑二分，把题目变成判定性问题：判断是否存在两个长度为 $k$ 的子串是相同的，且不重叠解决这个问题的关键还是利用 $height$，把排序后的后缀分成若干组，其中每组的后缀之间的 $height$ 值都不小于 $k$，有希望成为最长公共前缀不小于 $k$ 的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的 $sa$ 值的最大值和最小值之差是否不小于 $k$。如果有一组满足，则说明存在，否则不存在。
时间复杂度 $O(n \log n)$
代码
1 | /******************************************************************************* |
「POJ3261」Milk Patterns
链接
题解
题意: 可重叠的 $k$ 次最长重复子串。
思路同上，分组然后二分判定就好了。
代码
1 | /******************************************************************************* |
「BZOJ2882」工艺
链接
题解
此题就是求字符串的最小循环表示，也可以用最小表示法，后缀自动机做。
由于此题的数据有 $0$，我们对于每个树先全部加上 $1$，把原串 $S$ 复制一遍变为 $SS$，我们再往后面加一个最大字符，然后构建后缀数组，找到 $sa[1]$ 所对应原串中的位置输出就可以了，即输出 $SS_{sa[1] \% n} \text{ ~ } SS_{sa[1] \% n + n - 1}$。
代码
1 | /******************************************************************************* |
「POJ 2406」Power Strings
链接
题解
*题意: * 如果一个字符串 $L$ 是由某个字符串 $S$ 重复 $R$ 次而得到的， 则称 $L$ 是一个连续重复串。$R$ 是这个字符串的重复次数，给你一个连续重复串 $L$，求 $R$ 的最大值。
此题就是后缀数组求连续重复子串的经典题，也可以用 KMP 做。
我们先构建 $S$ 的后缀数组，枚举长度 $k$，然后判断是否满足以下条件 ($S$ 的循环节):
- $len(s) % k = 0$
- $lcp(Suffix(0), Suffix(k)) = n - k$
我们可以这样理解，再拿一个串 $S’$ 在原串 $S$ 下匹配，枚举长度 $k$ 即为从 $S’_k$ 开始匹配，判断 $S$ 与 $S’$ 匹配长度是否恰为总长 - 跳过的长度，即 $n - k$。
代码
1 | /******************************************************************************* |
字符串匹配
字符串匹配有很多做法，这里记录一下后缀数组的做法，这里只实现了单串匹配 $O(m \log n)$ 的做法，$O(m + \log n)$ 的做法详见论文。
实现
我们可以利用后缀数组字典序的单调性，通过二分在 $O(m \log n)$ 的时间内完成，其中 strncmp(s1, s2, size) 函数的作用是比较 $s_1, s_2$ 前 $size$ 个字符，如果不同，则返回第一个不同位置 $k$ 的 $s_1[k] - s_2[k]$。
代码
1 | /******************************************************************************* |
