企业官网建设流程全解析

比较两个长度为L的字符串是否相等，朴素做法是逐字符比对，O(L)。如果要在文本里找所有长度为L的重复子串，朴素做法就是O(n·L)——字符串一长就吃不消。

**字符串哈希（Rabin-Karp）**的思路极其朴素粗暴：给每个字符串算一个整数指纹，比对两个串就变成比对两个整数，O(1)。

真正精彩的是“滚动”——相邻窗口的指纹存在递推关系，能从上一个窗口O(1)推出下一个，于是滑动整个文本只需O(n)。

这条路线和KMP形成鲜明对照：

今天这两条路线我们都要跑一遍，还会给出实测对比。

📦 题目速览（30秒读懂）

题目1：重复的DNA序列（LC.187）

DNA由A/C/G/T组成，找出所有出现不止一次的长度为10的子串。

示例："AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"→["AAAAACCCCC","CCCCCAAAAA"]
约束：长度 ≤ 1e5。

题目2：最长重复子串（LC.1044，延伸）

返回任意一个最长重复子串，不存在返回""。

示例："banana"→"ana"（"na"也合法）

🧠 核心思路：多项式哈希 + 滚动递推

多项式哈希（进制表示）

最常用的哈希公式：

h(s) = ( c₀·B^(L-1) + c₁·B^(L-2) + ... + c_{L-1}·B⁰ ) mod M

其中cᵢ是字符的数值编码，B是进制（基数），M是模数。直观理解：把字符串当成B进制的一个大整数。

关键：滚动（Rolling）

设窗口长度为 L，窗口s[i-L+1 .. i]的哈希为h，要推出下一个窗口的哈希：

h' = ( h − val(s[i-L+1])·B^(L-1) ) · B + val(s[i+1])

翻译成人话：去掉最左字符的贡献 → 整体左移一位（乘B）→ 加上最右新字符。三步都是O(1)。

工程上有三个必须讲清的坑

1. 模数M的选择：必须是大质数（如10⁹+7）。若M与B不互质，哈希分布会严重退化。
2. 溢出处理：h·B很容易溢出。Python无所谓，Java/C++ 要么用long+ 及时取模，要么用无符号64位自然溢出当模数。
3. 碰撞：不同串可能算出同一个指纹。工程解法是双哈希（两个不同的B/M各算一遍），或“指纹相等后再逐字符兜底比对”。

🖼️ 图解算法（手把手走一遍）

以s = "AAAAACCCCC"、B = 4为例。编码A=0, C=1, G=2, T=3。

窗口s[0..9] = "AAAAACCCCC"：

滑到下一个窗口"AAAACCCCCA"：

1. 去掉最左：减去val(s[0])·B⁹ = 0
2. 左移一位：h ← h·B
3. 加新字符：h ← h + val(s[10]) = h + 0

每一步O(1)，与窗口长度L完全无关。

完整扫描：

最终答案["AAAAACCCCC","CCCCCAAAAA"]✓

💻 代码实现（Python + Java）

Python（LC.187滚动哈希版）

classSolution:deffindRepeatedDnaSequences(self,s:str)->list[str]:n,L=len(s),10ifn<=L:return[]MOD=10**9+7# 大质数模数BASE=4# 只有4种字符val={'A':0,'C':1,'G':2,'T':3}power=pow(BASE,L-1,MOD)# B^(L-1)：最左字符的权重seen=set()ans=set()h=0fori,chinenumerate(s):ifi>=L:# 先移除滑出的字符h=(h-val[s[i-L]]*power)%MOD h=(h*BASE+val[ch])%MOD# 再左移加新字符ifi>=L-1:ifhinseen:ans.add(s[i-L+1:i+1])else:seen.add(h)returnlist(ans)

Java（LC.187）

classSolution{publicList<String>findRepeatedDnaSequences(Strings){intn=s.length(),L=10;List<String>res=newArrayList<>();if(n<=L)returnres;finallongMOD=1_000_000_007L;finallongBASE=4;longpower=1;for(inti=0;i<L-1;i++)power=power*BASE%MOD;Set<Long>seen=newHashSet<>();Set<String>ans=newHashSet<>();longh=0;for(inti=0;i<n;i++){if(i>=L){h=(h-value(s.charAt(i-L))*power%MOD+MOD)%MOD;}h=(h*BASE+value(s.charAt(i)))%MOD;if(i>=L-1&&!seen.add(h)){ans.add(s.substring(i-L+1,i+1));}}res.addAll(ans);returnres;}privateintvalue(charc){switch(c){case'A':return0;case'C':return1;case'G':return2;default:return3;}}}

⚠️防坑提醒（必看）：

• 顺序：先移除滑出字符，再乘B加新字符。反过来写就要用B^L作为移除权重——混用必错。
• Java里(h - x + MOD) % MOD的+ MOD不能省——减法可能产生负数。
• seen.add(h)返回false说明已存在，直接加入答案。

区间指纹公式是怎么来的？

LC.1044里那个get_hash(l, r) = prefix[r] - prefix[l]·B^(r-l)看着像天书，其实只是两个前缀哈希做减法。

定义prefix[i] = h(s[0..i-1])。注意prefix[l]的最高次是B^(l-1)，而它在prefix[r]里应该对应B^(r-1)——差了B^(r-l)倍。所以把prefix[l]乘上B^(r-l)再减，前l个字符的贡献就精确抵消。

这个“最高次对齐”是所有前缀类技巧的通用套路：前缀和不需要乘系数，是因为加法里各位权重相同；而多项式哈希里每一位的权重是B的幂，所以必须补上倍数差。

延伸：LC.1044最长重复子串（滚动哈希 + 二分答案）

classSolution:deflongestDupSubstring(self,s:str)->str:n=len(s)# 双哈希参数MOD1,MOD2=10**9+7,10**9+9BASE1,BASE2=31,131nums=[ord(c)-ord('a')+1forcins]# 预处理两套幂次和前缀哈希pow1=[1]*(n+1)pow2=[1]*(n+1)pre1=[0]*(n+1)pre2=[0]*(n+1)foriinrange(n):pow1[i+1]=pow1[i]*BASE1%MOD1 pow2[i+1]=pow2[i]*BASE2%MOD2 pre1[i+1]=(pre1[i]*BASE1+nums[i])%MOD1 pre2[i+1]=(pre2[i]*BASE2+nums[i])%MOD2defget_hash(l:int,r:int):"""返回子串s[l:r] 的双哈希值"""h1=(pre1[r]-pre1[l]*pow1[r-l])%MOD1 h2=(pre2[r]-pre2[l]*pow2[r-l])%MOD2return(h1,h2)defcheck(length:int)->int:"""检查是否存在长度为length的重复子串，存在则返回起始下标，否则返回-1"""iflength==0:return0seen={}foriinrange(n-length+1):key=get_hash(i,i+length)ifkeyinseen:# 双哈希都相同后，再做一次字符串验证，彻底杜绝碰撞ifs[seen[key]:seen[key]+length]==s[i:i+length]:returnielse:seen[key]=ireturn-1# 二分搜索最长重复子串的长度lo,hi=1,n-1best_start,best_len=0,0whilelo<=hi:mid=(lo+hi)//2start=check(mid)ifstart!=-1:best_start,best_len=start,mid lo=mid+1else:hi=mid-1returns[best_start:best_start+best_len]ifbest_len>0else""

二分为什么成立？存在长度为L的重复子串 → 一定存在长度 ≤ L的重复子串（取其子串即可）。“存在性”对长度单调，所以可以二分。这又是二分答案的一次落地。

⏱️ 复杂度分析（面试必问）

实测：滚动哈希到底快多少？

DNA串长200,000（CPython3.13）：

短窗口下切片反而更快——CPython的切片是C层memcpy，常数极小；而滚动哈希每步要做两次乘法 + 取模。只有当L大到1000 时，O(1)递推的优势才压过常数。

那滚动哈希的价值在哪？不在“更快”，而在“能做到切片做不到的事”：

1. O(1)取任意长度区间的指纹——LC.1044二分时每轮要取所有长度mid的子串指纹，切片给不了这个能力。
2. 窗口长度极大时（L=10⁵），切片要复制n·L字节，滚动哈希照样O(n)。
3. 内存：只存8字节整数 vs 存子串对象，差一个量级。

方法论提醒：复杂度记号只描述增长趋势，不描述谁在小规模下更快。

🚀 举一反三：5道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

Q1：哈希碰撞怎么办？

三个层次：
①选大质数模数（10⁹+7）；
②双哈希——两组(B, M)各算一遍，碰撞概率降到约1/M²；
③兜底比对——指纹相等后再逐字符核一次。

把风险量化一下（面试加分项）。由生日悖论，期望碰撞对数约为：

E ≈ C(N, 2) / M ≈ N² / (2M)

代入N ≈ 10⁵、M = 10⁹+7：E ≈ 10¹⁰ / (2 × 10⁹) ≈ 5 对。

也就是说，单哈希跑满数据时，期望有5对左右不同的DNA片段指纹撞车——这解释了为什么网上不少“单哈希过LC.187”的题解，在大规模随机数据上偶尔WA。

上双哈希后，期望碰撞对数变成5 × 10⁻¹⁸——宇宙寿命尺度上都不会发生一次。这就是为什么“工程实现必须双哈希”不是玄学，是算出来的。

Python还有个偷懒方案：干脆不取模，用大整数当指纹（精确无碰撞），代价是整数膨胀、乘法变慢，仅建议小数据使用。

Q2：为什么叫“滚动”？

相邻窗口的指纹存在递推关系：h' = (h − 最左字符贡献) · B + 新字符。
窗口像轮子在文本上滚过去，指纹跟着滚，每步O(1)。

Q3：模数怎么选？有什么坑？

必须选大质数，且与基数B互质。
常见坑：
① 用2^64自然溢出时，若B取偶数会与模数不互质，分布退化；
② 模数太小（如10^4）时，n稍大就必然碰撞。

Q4：Rabin-Karp的最坏复杂度是多少？

O(nm)。如果每个窗口的指纹都碰撞，每次都要逐字符兜底比对，就退化成朴素算法。但随机数据下期望是O(n+m)。

🧩 实战小技巧（刷题党必备）

• 口诀：多项式哈希压整数，滚动递推O(1)；先减最左再乘加，双哈希防碰撞。
• 模板：h' = (h − 最左·B^(L-1))·B + 新字符，注意顺序。
• 防坑：Java减法加MOD；区间哈希补B^(r-l)。

📈 实际应用场景（不止是刷题）

• 论文查重 / 代码查重：把文档切成固定长度片段做指纹比对
• 文件同步：rsync的滚动校验和就是这一思想的工程实现
• 生物信息学：DNA序列的重复片段搜索（本题的来源场景）
• 最长公共子串 / 回文检测：都可转为哈希比对

🎁 今日思考题

LC.187里我用BASE = 4（因为只有4种字符）。如果改成BASE = 26或BASE = 31，会发生什么？是更快、更慢，还是更容易碰撞？