119-字符串-字符串哈希

核心概述

字符串哈希以滚动哈希在字串比较、子串判等与集合判重中提供近似常数时间的指纹检索能力，契合本仓库字符串模板的接口与语义。

原文引述

KACTL algorithms should be: useful, short, fast enough, well tested, and if relevant, readable and easy to modify. They should not be overly generic, since code is manually typed and that just adds overhead. ——摘自 kactl/README.md

展开阐述

• 定义与背景

  • 将字符串映射为整数指纹，支持 O(1) 子串哈希查询并以此实现快速等价判断、集合判重与模式定位（概率正确）。
  • 常见做法为单模或双模多项式滚动哈希；本节点不引入仓库外实现细节，仅给出语义与约定。

• 接口与输入输出语义（按仓库约定）

  • 典型接口（据约定风格）：
    • build(s)：预处理串 s，生成前缀哈希与幂表。
    • get(l, r) → 哈希值：返回区间 [l, r) 的子串指纹（按实现可能返回单模或 pair）。
    • concat(h1, h2, len2) → 连接后的指纹（若实现提供此能力）。
  • 语义：
    • get 的比较等价于“高概率等价”；如需更强鲁棒性，可采用多模组合或与确定性方法（如 118-字符串-AC自动机 的结构性匹配）搭配。

• 核心流程与关键要点

  • 预处理：构建前缀哈希 P[i] 与幂表 pow[i]。
  • 查询：子串哈希 H(l,r) = 归一化(P[r] − P[l]·pow[r−l])（依实现处理负数或溢出）。
  • 碰撞处理：通过双模或不同参数组合降低碰撞概率；在关键路径可引入二次确认（如长度或索引比对）。
  • 应用示例语义：
    • 去重：对多段子串取哈希置于容器（可参考 005-数据结构-哈希表 的工程取舍）。
    • 比较：两个子串哈希相等则判等（概率意义）。

• 复杂度与边界条件

  • 预处理 O(n)；单次子串查询 O(1)。
  • 边界：空串与空区间；索引越界；大小写/字符集映射的一致性。

• 与相邻技术的取舍对比

  • 相比确定性自动机/后缀结构，哈希实现简单、常数小，但存在极小概率碰撞。
  • 多模式匹配更适合 118-字符串-AC自动机；需要字典序与子串排序等可参考后缀结构（见蓝图相邻条目）。

关联节点

• 118-字符串-AC自动机
• 005-数据结构-哈希表