如何使用后缀数组（suffix array）求解n个字符串的最长公共子串

核心逻辑 #

两两比对的方法之所以会出错，是因为前两个字符串的最长公共子串不一定会出现在所有剩余字符串中，而基于后缀数组的方法可以一次性覆盖所有字符串的所有子串，避免局部最优的问题。

具体实现步骤 #

步骤1：拼接所有输入字符串 #

选取 n-1个互不相同、且从未出现在任何原输入字符串中的字符 作为分隔符，将所有输入字符串拼接为一个长字符串。
比如你给出的3个字符串示例，可以选#、$作为分隔符，拼接结果为 ABZDCC#ABZDEC$EFGHIC。
注意：分隔符的字典序需小于原字符串的所有字符，避免不同原字符串的后缀匹配时将分隔符计入公共前缀

步骤2：构建后缀数组与LCP数组 #

• 后缀数组（SA）：存储拼接后长字符串的所有后缀按字典序排序后的起始下标
• LCP数组（最长公共前缀数组）：LCP[i] 表示排序后第i个后缀和第i-1个后缀的最长公共前缀长度

步骤3：滑动窗口扫描LCP数组求最大值 #

我们需要在LCP数组上找到一个连续窗口，满足窗口覆盖的所有后缀分别来自n个不同的原字符串，窗口内的最小LCP值就是该窗口所有后缀的公共前缀长度，我们的目标是找到所有符合条件窗口中的最大最小LCP值。
具体可以用双指针维护滑动窗口：

• 维护计数数组，记录当前窗口内来自每个原字符串的后缀数量，以及当前窗口覆盖的不同原字符串总数
• 右指针不断右移，纳入新的后缀，对应原字符串计数加1，如果计数从0变为1，覆盖总数加1
• 当覆盖总数等于n时，尝试左移左指针缩小窗口，同步更新窗口内的最小LCP值，记录过程中出现的最大值

步骤4：还原最长公共子串 #

得到最大符合要求的LCP值k后，从对应窗口中任意取一个后缀，截取前k个字符，就是n个字符串的最长公共子串。

示例验证 #

输入的三个字符串：ABZDCC、ABZDEC、EFGHIC
拼接后构建的后缀数组排序后，末尾存在连续三个后缀分别来自三个不同的原字符串，且都以C开头，对应的窗口最小LCP值为1，因此得到最长公共子串为C，与实际结果一致。

内容的提问来源于stack exchange，提问作者MD. MEHEDI IMAM