寻找长度大于2的重复子串：除暴力法外的最优解决方案

给定字符串（示例输入：SpringisHereAgainSpringHere），要找出所有长度大于2的重复子串（示例输出：Spr,Spri,Spring,here,her），下面是几种比暴力法更高效的实现思路：

1. 滑动窗口 + 哈希表 #

• 核心思路：先遍历所有可能的子串长度（从3开始，最长到字符串长度的一半——毕竟超过一半的子串不可能重复出现两次），对每个长度L，用滑动窗口切出所有长度为L的子串，用哈希表记录每个子串的出现次数，最后收集出现过至少两次的子串。
• 细节优化：如果担心哈希冲突，可以用双哈希（同时维护两种不同哈希函数的结果），或者直接用语言内置的字符串哈希（比如Python的hash()，但生产环境建议用更可靠的哈希实现）。
• 示例代码（Python）：

def find_repeated_substrings(s):
    n = len(s)
    result = set()
    # 遍历所有符合要求的子串长度
    for sub_len in range(3, n // 2 + 1):
        seen_subs = set()
        for start in range(n - sub_len + 1):
            current_sub = s[start:start+sub_len]
            if current_sub in seen_subs:
                result.add(current_sub)
            else:
                seen_subs.add(current_sub)
    # 转成示例要求的逗号分隔格式
    return ','.join(result)

# 测试示例输入
input_str = "SpringisHereAgainSpringHere"
print(find_repeated_substrings(input_str))

• 优势：时间复杂度为O(n²)，比暴力法的O(n³)高效很多，适合处理中等长度的字符串。

2. 后缀数组法 #

• 核心思路：把字符串的所有后缀生成一个数组，然后对这个数组排序。排序后，重复的子串必然出现在相邻的后缀中，只需要计算相邻后缀的最长公共前缀（LCP），如果LCP长度≥3，那么这个前缀里所有长度≥3的子串都是重复子串。
• 细节优化：生成后缀数组可以用SA-IS算法（时间复杂度O(n)），计算LCP数组用Kasai算法（时间复杂度O(n)），整体效率极高。
• 优势：时间复杂度可达O(n)，专门适合处理超长字符串的子串问题。

3. 后缀自动机法 #

• 核心思路：后缀自动机是一种紧凑的字符串结构，能在O(n)时间内构建完成。构建后，遍历自动机的每个状态——每个状态代表一类等价的子串，只要某个状态对应的子串出现次数≥2（即endpos集合大小≥2），且子串长度≥3，就收集这些子串（注意去重）。
• 优势：时间和空间复杂度都是O(n)，是当前处理这类子串重复问题的最优解法之一，适合大规模字符串处理场景。

内容的提问来源于stack exchange，提问作者Hello