本文共 2013 字，大约阅读时间需要 6 分钟。

今天看了后缀数组的应用，整理一下相关内容：

2.2 单个字符串的相关问题

这一类问题的常用做法是先求后缀数组和 height 数组，然后利用 height 数组进行求解。

2.2.1 重复子串

重复子串：字符串 R 在字符串 L 中至少出现两次，则称 R 是 L 的重复子串。

2.2.2 可重叠最长重复子串

给定一个字符串，求最长重复子串，这两个子串可以重叠。

算法分析：

这道题是后缀数组的一个简单应用。做法比较简单，只需要求 height 数组里的最大值即可。最长重复子串的长度就是 height 数组里的最大值。这个做法的时间复杂度为 O(n)。

2.2.3 不可重叠最长重复子串（Pku1743）

给定一个字符串，求最长重复子串，这两个子串不能重叠。

算法分析：

这题比上一题稍复杂一点。先二分答案，把题目变成判定性问题：判断是否存在两个长度为 k 的子串是相同的，且不重叠。解决这个问题的关键还是利用 height 数组。把排序后的后缀分成若干组，其中每组的后缀之间的 height 值都不小于 k。例如，字符串为“aabaaaab”，当 k=2 时，后缀分成了 4 组，如图 5。

2.2.4 可重叠的 k 次最长重复子串（Pku3261）

给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。

算法分析：

这题的做法和上一题差不多，也是先二分答案，然后将后缀分成若干组。不同的是，这里要判断的是有没有一个组的后缀个数不小于 k。如果有，那么存在 k 个相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn)。

2.2.5 不相同的子串的个数（Spoj694、Spoj705）

给定一个字符串，求不相同的子串的个数。

算法分析：

每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不相同的前缀的个数。如果所有的后缀按照 suffix(sa[1]), suffix(sa[2]), suffix(sa[3]), …… ,suffix(sa[n])的顺序计算，不难发现，对于每一次新加进来的后缀 suffix(sa[k]), 它将产生 n-sa[k]+1 个新的前缀。但是其中有 height[k] 个是和前面的字符串的前缀是相同的。所以 suffix(sa[k]) 将“贡献”出 n-sa[k]+1- height[k] 个不同的子串。累加后便是原问题的答案。这个做法的时间复杂度为 O(n)。

2.2.6 回文子串

如果将字符串 L 的某个子字符串 R 反过来写后和原来的字符串 R 一样，则称字符串 R 是字符串 L 的回文子串。

2.2.7 最长回文子串（Ural1297）

给定一个字符串，求最长回文子串。

算法分析：

穷举每一位，然后计算以这个字符为中心的最长回文子串。注意这里要分两种情况，一是回文子串的长度为奇数，二是长度为偶数。两种情况都可以转化为求一个后缀和一个反过来写的后缀的最长公共前缀。具体的做法是：将整个字符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变成了求这个新的字符串的某两个后缀的最长公共前缀。如图 6 所示。

2.2.8 连续重复子串

如果一个字符串 L 是由某个字符串 S 重复 R 次而得到的，则称 L 是一个连续重复串。R 是这个字符串的重复次数。

2.2.9 连续重复子串（Pku2406）

给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的，求 R 的最大值。

算法分析：

做法比较简单，穷举字符串 S 的长度 k，然后判断是否满足。判断的时候，先看字符串 L 的长度能否被 k 整除，再看 suffix(1) 和 suffix(k+1) 的最长公共前缀是否等于 n-k。在询问最长公共前缀的时候，suffix(1) 是固定的，所以 RMQ 问题没有必要做所有的预处理，只需求出 height 数组中的每一个数到 height[rank[1]] 之间的最小值即可。整个做法的时间复杂度为 O(n)。

2.2.10 重复次数最多的连续重复子串（Spoj687、Pku3693）

给定一个字符串，求重复次数最多的连续重复子串。

算法分析：

先穷举长度 L，然后求长度为 L 的子串最多能连续出现几次。首先连续出现 1 次是肯定可以的，所以这里只考虑至少 2 次的情况。假设在原字符串中连续出现 2 次，记这个子字符串为 S，那么 S 肯定包括了字符 r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以只须看字符 r[L*i] 和 r[L*(i+1)] 往前和往后各能匹配到多远，记这个总长度为 K，那么这里连续出现了 K/L+1 次。最后看最大值是多少。如图 7 所示。

以上内容主要引自许智磊《后缀数组》论文，写得非常好，有兴趣的可以参考一下。