企业官网建设流程全解析

字符串哈希与子串哈希概述

• 定义字符串哈希及其应用场景（如字符串匹配、重复子串检测）
• 子串哈希的核心作用：快速计算任意子串的哈希值

常见字符串哈希方法

• 多项式滚动哈希
  • 公式：H(s)=(s0⋅pn−1+s1⋅pn−2+⋯+sn−1⋅p0)mod mH(s) = (s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + \dots + s_{n-1} \cdot p^0) \mod mH(s)=(s0​⋅pn−1+s1​⋅pn−2+⋯+sn−1​⋅p0)modm
  • 参数选择：基数ppp和模数mmm的选取原则（如p=31p=31p=31，m=109+7m=10^9+7m=109+7，通常选择质数）
• 双哈希方法
  • 使用两组不同的(p,m)(p, m)(p,m)降低碰撞概率

子串哈希的预处理与查询

• 前缀哈希数组预处理
  • 定义前缀哈希数组hhh和幂次数组powspowspows：

    h[i]=(h[i-1]*p+s[i])%m;pows[i]=(pows[i-1]*p)%m;

• 子串哈希计算公式
  • 公式：H(s[l..r])=(h[r]−h[l−1]⋅pr−l+1)mod mH(s[l..r]) = (h[r] - h[l-1] \cdot p^{r-l+1}) \mod mH(s[l..r])=(h[r]−h[l−1]⋅pr−l+1)modm
  • 边界处理与取模修正

代码实现示例（C++）

vector<int>compute_subhash(conststring&s,intp,intm){intn=s.size();vector<int>h(n+1,0),pows(n+1,1);for(inti=0;i<n;++i){h[i+1]=(h[i]*p+s[i])%m;pows[i+1]=(pows[i]*p)%m;}return{h,pows};}intget_hash(constvector<int>&h,constvector<int>&pows,intl,intr,intm){return(h[r]-h[l-1]*pows[r-l+1]%m+m)%m;}

应用场景与优化

• 快速比较子串：比较两个子串的哈希值是否相等
• 最长回文子串：结合二分搜索与哈希优化
• 哈希冲突处理：双哈希、大质数模数的选择策略

注意事项

• 哈希冲突的可能性与解决方案
• 时间与空间复杂度的权衡（预处理O(n)O(n)O(n)，查询O(1)O(1)O(1)）