查找无空格超长字符串中长度≥4的重复子串

核心思路 #

要搞定这个问题，核心就是遍历所有可能的子串长度（从4开始，到字符串长度的一半为止），对每个长度用滑动窗口生成所有子串并统计出现次数，最后筛选出出现至少两次的子串。如果字符串特别长，还可以用滚动哈希（Rabin-Karp）优化性能，避开暴力枚举的高时间复杂度。

分步实现方案 #

1. 基础暴力解法（适合中等长度字符串）

如果你的字符串长度不是特别夸张（比如几十万字符以内），暴力解法简单又直观：

• 遍历子串长度 l，范围从4到 len(s)//2（毕竟长度超过字符串一半的子串，最多只能出现一次，不可能重复）
• 对每个长度 l，用滑动窗口扫遍整个字符串，生成所有长度为 l 的子串
• 用字典记录每个子串的出现次数，只要某个子串出现第二次，就加入结果集合（避免重复添加）
• 最后把集合转成列表返回，自动去重

def find_repeated_substrings(s, min_length=4):
    repeated = set()
    n = len(s)
    max_len = n // 2
    # 遍历所有符合要求的子串长度
    for l in range(min_length, max_len + 1):
        substr_counts = {}
        # 滑动窗口生成子串
        for i in range(n - l + 1):
            substr = s[i:i+l]
            if substr in substr_counts:
                substr_counts[substr] += 1
                # 第一次检测到重复就加入集合，后续不用再处理
                if substr_counts[substr] == 2:
                    repeated.add(substr)
            else:
                substr_counts[substr] = 1
    return list(repeated)

# 示例测试
s = "abcdtextsampleabcdtextsamplexyz"
print(find_repeated_substrings(s))
# 输出: ['abcd', 'text', 'sample']

2. 滚动哈希优化（适合超长篇字符串）

如果字符串长度达到百万级别，暴力解法的O(n²)时间复杂度会慢到离谱。这时候可以用Rabin-Karp滚动哈希算法，通过计算子串的哈希值快速比较是否重复，避免每次生成完整子串的开销：

def rabin_karp_find_repeats(s, min_length=4):
    repeated = set()
    n = len(s)
    max_len = n // 2
    base = 911382629  # 用大质数做基数降低碰撞概率
    mod = 10**18 + 3   # 大模数进一步减少哈希冲突

    for l in range(min_length, max_len + 1):
        # 计算初始窗口的哈希值
        current_hash = 0
        power = pow(base, l-1, mod)
        for i in range(l):
            current_hash = (current_hash * base + ord(s[i])) % mod
        
        hash_counts = {current_hash: [0]}  # 哈希值对应子串的起始索引列表
        # 滑动窗口更新哈希值
        for i in range(1, n - l + 1):
            # 移除窗口左侧字符的哈希影响
            current_hash = (current_hash - ord(s[i-1]) * power) % mod
            # 加入窗口右侧新字符的哈希值
            current_hash = (current_hash * base + ord(s[i+l-1])) % mod
            
            if current_hash in hash_counts:
                # 哈希可能碰撞，必须验证实际子串是否相同
                for idx in hash_counts[current_hash]:
                    if s[idx:idx+l] == s[i:i+l]:
                        repeated.add(s[i:i+l])
                        break
                hash_counts[current_hash].append(i)
            else:
                hash_counts[current_hash] = [i]
    return list(repeated)

关键注意事项 #

• 去重处理：用集合存储结果能自动去重，避免同一个子串被多次统计
• 哈希碰撞：滚动哈希虽然能大幅提升效率，但仍有极小概率碰撞，所以一定要加实际子串的验证步骤，避免误判
• 性能权衡：暴力解法实现简单，适合中小字符串；滚动哈希适合超长字符串，时间效率更高
• 长度上限：把最大子串长度设为len(s)//2是因为，超过这个长度的子串最多只能出现一次，不可能重复

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