字符串哈希与子串哈希概述定义字符串哈希及其应用场景如字符串匹配、重复子串检测子串哈希的核心作用快速计算任意子串的哈希值常见字符串哈希方法多项式滚动哈希公式H(s)(s0⋅pn−1s1⋅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−1s1⋅pn−2⋯sn−1⋅p0)modm参数选择基数ppp和模数mmm的选取原则如p31p31p31m1097m10^97m1097通常选择质数双哈希方法使用两组不同的(p,m)(p, m)(p,m)降低碰撞概率子串哈希的预处理与查询前缀哈希数组预处理定义前缀哈希数组hhh和幂次数组powspowspowsh[i](h[i-1]*ps[i])%m;pows[i](pows[i-1]*p)%m;子串哈希计算公式公式H(s[l..r])(h[r]−h[l−1]⋅pr−l1)mod mH(s[l..r]) (h[r] - h[l-1] \cdot p^{r-l1}) \mod mH(s[l..r])(h[r]−h[l−1]⋅pr−l1)modm边界处理与取模修正代码实现示例Cvectorintcompute_subhash(conststrings,intp,intm){intns.size();vectorinth(n1,0),pows(n1,1);for(inti0;in;i){h[i1](h[i]*ps[i])%m;pows[i1](pows[i]*p)%m;}return{h,pows};}intget_hash(constvectorinth,constvectorintpows,intl,intr,intm){return(h[r]-h[l-1]*pows[r-l1]%mm)%m;}应用场景与优化快速比较子串比较两个子串的哈希值是否相等最长回文子串结合二分搜索与哈希优化哈希冲突处理双哈希、大质数模数的选择策略注意事项哈希冲突的可能性与解决方案时间与空间复杂度的权衡预处理O(n)O(n)O(n)查询O(1)O(1)O(1)
字符串哈希 - 子串哈希公式
字符串哈希与子串哈希概述定义字符串哈希及其应用场景如字符串匹配、重复子串检测子串哈希的核心作用快速计算任意子串的哈希值常见字符串哈希方法多项式滚动哈希公式H(s)(s0⋅pn−1s1⋅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−1s1⋅pn−2⋯sn−1⋅p0)modm参数选择基数ppp和模数mmm的选取原则如p31p31p31m1097m10^97m1097通常选择质数双哈希方法使用两组不同的(p,m)(p, m)(p,m)降低碰撞概率子串哈希的预处理与查询前缀哈希数组预处理定义前缀哈希数组hhh和幂次数组powspowspowsh[i](h[i-1]*ps[i])%m;pows[i](pows[i-1]*p)%m;子串哈希计算公式公式H(s[l..r])(h[r]−h[l−1]⋅pr−l1)mod mH(s[l..r]) (h[r] - h[l-1] \cdot p^{r-l1}) \mod mH(s[l..r])(h[r]−h[l−1]⋅pr−l1)modm边界处理与取模修正代码实现示例Cvectorintcompute_subhash(conststrings,intp,intm){intns.size();vectorinth(n1,0),pows(n1,1);for(inti0;in;i){h[i1](h[i]*ps[i])%m;pows[i1](pows[i]*p)%m;}return{h,pows};}intget_hash(constvectorinth,constvectorintpows,intl,intr,intm){return(h[r]-h[l-1]*pows[r-l1]%mm)%m;}应用场景与优化快速比较子串比较两个子串的哈希值是否相等最长回文子串结合二分搜索与哈希优化哈希冲突处理双哈希、大质数模数的选择策略注意事项哈希冲突的可能性与解决方案时间与空间复杂度的权衡预处理O(n)O(n)O(n)查询O(1)O(1)O(1)
