Golang实现基于前缀和算法的字符串重复块查找与定位-Golang-PHP中文网

前缀哈希（非前缀和）配合双模数滚动哈希，将子串比较从o(n)降至o(1)，支撑o(n log n)二分求最长重复子串；关键在预处理h[i]与p[i]、非重叠判断及防哈希碰撞。

golang实现基于前缀和算法的字符串重复块查找与定位

为什么用前缀和而不是暴力匹配

字符串中找重复子串（比如连续出现两次以上的 abab），暴力枚举所有子串再两两比对，时间复杂度是 O(n⁴) —— 既慢又难写边界。前缀和本身不直接解决字符串重复问题，但配合 hash 和滚动哈希（如 Rabin-Karp），能快速算出任意子串的哈希值，把“比较子串是否相等”从 O(n) 降到 O(1)。这才是实际落地的关键。

真正起作用的是「前缀哈希数组」：定义 h[i] 为 s[0:i] 的哈希值，再配一个幂次数组 p[i] = base^i mod mod，就能在 O(1) 内计算 s[l:r] 的哈希：
hash(l, r) = (h[r] - h[l] * p[r-l]) % mod

必须用双模数（如 mod1=1e9+7, mod2=1e9+9）防哈希碰撞，单模基本不可靠
base 推荐选 131 或 13331，避免与常见字符 ASCII 值冲突
数组下标从 0 开始，h[0]=0，h[i] 对应前 i 个字符，别搞反

如何定位长度固定的重复块（如找所有长度为 L 的重复子串）

给定固定长度 L，目标是找出所有在字符串中至少出现两次、且位置不重叠的子串。这时不需要枚举所有长度，只需对每个起始位置 i 计算 hash(i, i+L)，用 map[[2]uint64][]int 存储哈希值到起始索引列表的映射。

关键点不在存，而在「去重」和「非重叠判断」：

Golang Spf13 Viper

Go 配置库，使用 spf13/viper — 分层优先级（flag > env >file > KV > default），提供 BindPFlag/BindPFlags、SetEnvPrefix + SetEnvKeyReplace 等功能。

下载

同一个哈希值对应多个位置时，只保留最早两个（足够判断是否重复），避免内存爆炸
判断是否非重叠：若 i 和 j 都是该子串的起始位置，需满足 abs(i - j) >= L，否则是重叠或相邻覆盖
别忘了预处理 h 和 p 数组——长度要开到 n+1，不然 h[n] 访问越界

怎么找最长重复子串（Longest Repeated Substring）

这是经典问题，不能枚举所有长度（太慢），要用二分答案：对长度 mid，调用上一节的固定长度检查逻辑，看是否存在满足条件的重复块。时间复杂度从 O(n³) 降到 O(n log n)。

实操注意点：

二分左边界设为 1，右边界设为 n/2（重复子串最长不超过一半）
每次检查时，清空哈希映射，别复用上一轮的 map 导致误判
找到最大长度后，想返回具体子串？得再跑一次该长度的扫描，取第一个命中位置的 s[i:i+maxLen] 即可
Go 中 map 遍历无序，如果需要稳定输出，得把结果存 slice 后排序

边界与性能陷阱：Go 实现时容易翻车的地方

Go 的整数溢出和取模行为很实在，不像 Python 自动大整数——所有中间计算都得手动 % mod，尤其 h[r] - h[l]*p[r-l] 可能为负，要写成 (h[r] - h[l]*p[r-l] + mod) % mod。

uint64 虽好，但双模仍建议用 int64 配 int64 模数，避免无符号减法绕回
别用 fmt.Sprintf("%s", s[i:j]) 当 key 存 map——字符串拷贝开销大，且长度长时内存飙升
构建前缀哈希时，循环里别写 h[i] = (h[i-1]*base + int(s[i-1])) % mod，Go 的 byte 是 uint8，直接加没问题，但明确转 int64 更安全
测试用例一定要包含全相同字符（如 "aaaa"）和空串/单字符，前者极易因重叠判断漏解，后者可能触发除零或越界