后缀数组应用

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

例 1：最长公共前缀
给定一个字符串，询问某两个后缀的最长公共前缀。
算法分析：
按照上面所说的做法，求两个后缀的最长公共前缀可以转化为求某个区间上的最小值。对于这个 RMQ 问题（如果对 RMQ 问题不熟悉，请阅读其他相关资料），可以用 O(nlogn)的时间先预处理，以后每次回答询问的时间为 O(1)。所以对于本问题，预处理时间为 O(nlogn)，每次回答询问的时间为 O(1)。如果 RMQ 问题用 O(n)的时间预处理，那么本问题预处理的时间可以做到 O(n)。 

２．２单个字符串的相关问题 
这类问题的一个常用做法是先求后缀数组和 height 数组，然后利用 height数组进行求解

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

例 2：可重叠最长重复子串
给定一个字符串，求最长重复子串，这两个子串可以重叠。
算法分析：
这道题是后缀数组的一个简单应用。做法比较简单，只需要求 height 数组里的最大值即可。首先求最长重复子串，等价于求两个后缀的最长公共前缀的最大值。因为任意两个后缀的最长公共前缀都是 height 数组里某一段的最小值，那么这个值一定不大于 height 数组里的最大值。所以最长重复子串的长度就是height 数组里的最大值。这个做法的时间复杂度为 O(n)。

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

容易看出，有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为O(nlogn)。

例 4：可重叠的 k 次最长重复子串（pku3261）给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。算法分析：这题的做法和上一题差不多，也是先二分答案，然后将后缀分成若干组。不同的是，这里要判断的是有没有一个组的后缀个数不小于 k。如果有，那么存在k 个相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn)。

２．２．２子串的个数 

例 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)。

 ２．２．３回文子串 ：

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

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

这个做法的时间复杂度为 O(nlogn)。如果 RMQ 问题用时间为 O(n)的方法预处理，那么本题的时间复杂度可以降为 O(n)。

２．２．４ 连续重复子串连续重复串：

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

例 7：连续重复子串(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)。

例 8：重复次数最多的连续重复子串(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 所示。

暂时先整理这么多，以上内容主要引自许智磊《后缀数组》论文 写的非常好，有兴趣的可以b可以拜读一下，链接我已经发在上篇博客里了。