“最长公共前缀数组”的最长子串变种：给定多个字符串，求它们的最长公共子串（要求子串在至少k个字符串中出现）

题目描述

我们有 \(N\) 个字符串（\(N \geq 2\)），每个字符串长度不超过 \(M\)。我们希望找到一个最长的子串，这个子串必须至少在 \(k\) 个不同的字符串中出现（\(2 \leq k \leq N\)）。
这里的“出现”是指子串作为连续片段存在于某个字符串中（允许在不同字符串中出现在不同位置）。

输入示例

N = 3, k = 2  
字符串：  
abcde  
bcdef  
cdefg

输出示例

最长公共子串长度 = 4（子串 "bcde" 在前两个字符串中都出现）

解题思路

这个问题可以用“后缀数组 + 二分答案 + 滑动窗口”解决，本质上是将多个字符串拼接成一个长串，然后利用后缀数组的公共前缀性质来判断是否有一段子串在至少 \(k\) 个原串中出现。

步骤拆解：

1. 拼接字符串并添加分隔符
   为了避免后缀跨越不同字符串时错误匹配，我们在每个字符串之间插入一个不在字符集中出现的分隔符（例如 '#'、'$' 等），并记录每个后缀属于哪个原字符串。

2. 构建后缀数组和 LCP 数组

   • 后缀数组（Suffix Array, SA）：将所有后缀按字典序排序。
   • 高度数组（LCP Array）：lcp[i] 表示后缀 SA[i] 与 SA[i-1] 的最长公共前缀长度。

3. 二分答案
   我们并不知道最长公共子串的长度是多少，但可以在 [0, M] 范围内二分查找长度 L，判断是否存在长度为 L 的子串在至少 \(k\) 个原串中出现。

4. 判断长度 L 是否可行

   • 遍历 LCP 数组，找到一段连续的区间 [l, r]，使得区间内所有相邻后缀的 LCP ≥ L（即这些后缀拥有长度至少为 L 的公共前缀）。
   • 检查区间内出现的原字符串编号（去重）是否 ≥ k。
   • 如果存在这样的区间，则长度 L 可行。

5. 输出结果
   二分结束后，我们得到了最大可行长度 ans，并可记录对应子串内容（如果需要输出具体子串，可额外保存区间信息）。

详细讲解

1. 字符串拼接与编号标记

假设我们有字符串 s1 = "abc", s2 = "bc"。
拼接后："abc#bc$"（分隔符 '#' 和 '$' 要互不相同，且小于所有字母，以保证后缀排序时正确处理）。
同时记录数组 belong[i] 表示后缀 i 属于哪个原字符串（从 0 开始编号）。

2. 后缀数组与 LCP 数组

• 后缀数组的构造可以用倍增法（O(n log n)）或 SA-IS（O(n)）。
• LCP 数组可以通过 Kasai 算法在 O(n) 内从 SA 构造。

3. 二分答案

设 low = 0, high = M（最长字符串长度）。
每次取 mid = (low + high + 1) / 2，判断是否存在长度为 mid 的公共子串出现在至少 k 个原串中。

4. 判断函数 check(L)

遍历 LCP 数组，维护一个滑动窗口：

cnt = {}  # 记录窗口内各原串编号出现次数
unique = 0  # 不同的原串编号数
left = 0
for right in range(1, n+1):
    # 将后缀 SA[right] 加入窗口
    id = belong[SA[right]]
    cnt[id] 增加 1
    if cnt[id] == 1:
        unique += 1
    
    # 如果 left+1 到 right 之间某个 LCP < L，则移动 left
    while left < right and LCP[left+1] < L:
        id_left = belong[SA[left]]
        cnt[id_left] 减少 1
        if cnt[id_left] == 0:
            unique -= 1
        left += 1
    
    if unique >= k:
        return True

注意：LCP 数组下标一般从 2 开始（或另做处理），上述伪代码为示意，实际需处理边界。

5. 复原子串（可选）

在判断过程中，如果找到满足条件的窗口 [l, r]，则公共前缀就是后缀 SA[l] 的前 L 个字符，即子串 T[SA[l] : SA[l]+L]。

复杂度分析

• 拼接后总长度 \(n = O(N \cdot M)\)。
• 后缀数组与 LCP 构造：O(n) 或 O(n log n)。
• 二分 + 滑动窗口检查：二分 O(log M)，每次检查 O(n)，总时间 O(n log M)。
• 空间 O(n)。

示例推演

N=3, k=2  
字符串：  
1: abcde  
2: bcdef  
3: cdefg

拼接："abcde#bcdef$cdefg%"（分隔符 #, $, % 互不相同且小于字母）。

构建 SA 与 LCP（略过详细排序过程）。

二分 L：

• L=5 时，检查是否存在长度为 5 的子串出现在至少 2 个原串中 → 没有（最长匹配是 "bcde" 长度 4）。
• L=4 时，检查到后缀 "bcde..."（来自串1）和 "bcdef..."（来自串2）的 LCP=4，且它们来自不同原串，满足条件。
• L=4 可行，继续尝试 L=5 不可行，最终答案=4。

总结

本题是多字符串最长公共子串的经典变种，通过“拼接+后缀数组+LCP+二分答案”巧妙地将子串查找转化为公共前缀的区间覆盖问题，是后缀数组的典型应用。它避免了枚举所有子串的 O(M²) 复杂度，适合处理较大规模输入。