上期，我们主要讲解了后缀数组在单字符串问题上的应用。在多字符串问题上，后缀数组是否仍然有优秀的表现呢？
答案显然是肯定的。
最长公共子串
Problem：给定两个字符串S和T，求这两个字符串的最长公共子串。
Solution：容易发现，一个字符串的子串，一定是该字符串的每个后缀的前缀。所以，求两个字符串的最长公共子串，只需要找这两个字符串的后缀的最长公共前缀就行了。
但是，问题在于如何对两个字符串使用后缀数组呢？
这里有一个小技巧。我们可以用一个在两个字符串中都没有出现的字符（例如特殊字符等）将这两个字符串连接到一起（这里是为了对新字符串进行截断），如下图所示：
Example
这样我们就把问题转化成：给定一个字符串，求这个字符串前一部分的后缀和后一部分的后缀的最长公共前缀的长度。由height数组的性质，我们只需判断相邻的两个后缀是否属于新字符串的不同部分。如果是，就能用该位置的height来更新答案。下面是一个例子：
Example
为什么不用把前半部分的后缀和后半部分的后缀两两求最长公共前缀呢？我们知道从一个后缀a开始，往后求a和任意一个后缀的最长公共前缀（设长度为L），L会小于之间任何一个height的值。所以，当一个后缀向后匹配超过一个后缀是没有必要的。
长度不小于k的公共子串的个数
Problem：给定两个字符串S和T，求这两个字符串中长度不小于k的公共子串的个数。其中，公共子串可以相同。
Solution：先考虑一个暴力的方法：先将字符串S和T用一个没出现过的字符连接起来得到新字符串A，然后求A的后缀数组，对于每一个S的后缀（即A的前半部分的后缀），我们可以统计它和每一个T的后缀的最长公共前缀。
这样的复杂度极高，那么有没有什么优化的方法呢？
我们可以尝试对A的后缀数组进行顺序遍历，遍历到一个S的后缀时，统计这个后缀与之前出现过的T的后缀的最长公共前缀。考虑height数组的性质，对于一个后缀sa[j]，sa[i] (1<=i<j) 和sa[j]的最长公共前缀随i的增大而增大。
所以，我们可以用一个数组q来维护处理到sa[j]时，出现过的T的后缀与sa[j]的最长公共前缀。通过前面的分析，我们知道数组q是单调递增的。所以，每次新扫过一个后缀，我们可以用二分的方法来更新数组q中的值。如果当前这个后缀是T的后缀，那么我们就把这个后缀加入数组q。否则就计算数组q中每一个后缀与当前后缀的最长公共前缀（即q数组中每一个元素的和）。
总结
我们介绍了后缀数组在两个字符串问题上的应用。多个字符串与之类似，我们只需要把多个字符串用没出现过的字符连接起来，求解后缀数组，然后依题意来判断即可。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
网友评论