前两期，我们重点介绍了后缀数组中sa、rank、height数组的求法。这些数组都具有优秀的性质，我来向大家介绍几种后缀数组在解决单字符串问题上的经典应用。
最长重复子串（可重叠）
Problem：若字符串A在字符串B中出现两次及以上，则称A为B的重复子串。给定字符串S，求S中出现位置可重叠的最长重复子串的长度。
Solution：回想height数组的定义，发现可重叠最长重复子串的长度就是height数组中的最大值。因为height数组表示排名相邻的后缀的最长公共前缀。显然，公共前缀一定是出现了两次以上的，所以最大的公共前缀的长度就是最长可重叠重复子串的长度。
最长重复子串（不可重叠）
Problem：问题描述与上题基本相同，但是要求重复子串的出现位置不可重叠。
Solution：考虑二分答案，把求值的问题变成判断是非的问题。假设二分得到k，我们按照sa数组的顺序把height大于等于k的后缀分成一组，如下图。
分组过后，我们发现每一组的任意两个后缀的最长公共前缀都是大于等于k的。这时，我们只要判断是否存在一组后缀，该组后缀里sa的最小值和最大值的差大于等于k就行了（sa存的是后缀的位置，两个相差大于等于k意味着公共前缀至少有k个字符不重叠）。
最长重复子串（可重叠，需重复k次）
Problem：这个问题依然和上述问题类似，但是要求重复子串的出现次数要大于等于k次。
Solution：问题一的方法在这个问题上显然是行不通的。我们仍然考虑二分答案并分组。这次每一组要判断的是否存在一组后缀，在该组后缀中后缀个数是否大于等于k即可。
不同子串的个数
Problem：求一个字符串中有多少个不同的子串。
Solution：假设我们已经统计出了前k个后缀有几个不同的子串，考虑新加一个后缀，这个后缀一共会产生n-sa[k+1]+1个新的子串（这里要求新的子串必须是该后缀的前缀，这样保证了每一个后缀产生的子串覆盖了原字符串的所有子串）。这些新产生的子串中，有n-sa[k+1]+1-height[k+1]个子串是不同的（去掉与其他字符串的公共前缀）。那么，不同子串的个数就很容易统计了。
重复次数最多的连续重复子串
Problem：求给定字符串的重复次数最多的连续重复子串。连续重复子串的定义是：若一个串S由T重复若干次得到，则称T为S的一个连续重复子串。
Solution：考虑枚举连续重复子串的长度为L。由抽屉原理我们知道，连续重复子串一定包含了S[0],S[L],S[2L]……中的相邻两个。我们可以用后缀数组求解S[iL],S[(i+1)*L]的往后能匹配多远（即最长公共前缀），往前能匹配多远（即把整个字符串反过来的“最长公共前缀”）。设总长度为K，类似于KMP求循环节的思想，则该连续重复子串的重复次数为K/L+1。
写在最后
对于单字符串问题，后缀数组还能做到KMP，Manacher等算法所能做到的事，如求回文串长度、最小循环节长度等，这里就不在赘述了，读者可以自行思考。
下期，我将为大家带来后缀数组在多字符串问题中的应用。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
