双模字符串哈希及其在子串匹配与去重中的应用
双模字符串哈希封装
采用两个互异的大质数作为模数，并配合随机基底，可显著降低哈希碰撞概率。本实现中，模数固定为标准大质数，基底亦为预设常量：
const long long MOD1 = 1000000007LL, BASE1 = 131542399LL;
const long long MOD2 = 1000000009LL, BASE2 = 986824513LL;
struct Hash2 {
long long a, b;
Hash2(long long x = 0, long long y = 0) : a(x % MOD1), b(y % MOD2) {}
Hash2 operator+(const Hash2& o) const {
return Hash2((a + o.a) % MOD1, (b + o.b) % MOD2);
}
Hash2 operator-(const Hash2& o) const {
return Hash2((a - o.a + MOD1) % MOD1, (b - o.b + MOD2) % MOD2);
}
Hash2 operator*(const Hash2& o) const {
return Hash2(a * o.a % MOD1, b * o.b % MOD2);
}
};
预处理各阶幂次以支持子串哈希的快速计算：
std::vector<Hash2> pw1, pw2;
void init_powers(int len) {
pw1.assign(len + 1, Hash2(1));
pw2.assign(len + 1, Hash2(1));
for (int i = 1; i <= len; i++) {
pw1[i] = pw1[i-1] * Hash2(BASE1);
pw2[i] = pw2[i-1] * Hash2(BASE2);
}
}
构建字符串哈希结构体，支持子串查询与单点修改：
struct StringHash {
std::string text;
std::vector<Hash2> h1, h2;
StringHash(const std::string& s = "") : text(s), h1(1, Hash2(1)), h2(1, Hash2(1)) {
for (char c : text) {
h1.emplace_back(h1.back() * Hash2(BASE1) + Hash2(c));
h2.emplace_back(h2.back() * Hash2(BASE2) + Hash2(c));
}
}
Hash2 substring(int l, int r) const {
int len = r - l + 1;
Hash2 hash1 = h1[r+1] - h1[l] * pw1[len];
Hash2 hash2 = h2[r+1] - h2[l] * pw2[len];
return hash1 * Hash2(pw2[len].a) + hash2; // 合并双哈希避免溢出最优顺序
}
Hash2 point_modify(int idx, char new_char) const {
char old = text[idx];
int len = static_cast<int>(text.size());
Hash2 delta1 = Hash2(new_char - old);
Hash2 delta2 = Hash2(new_char - old);
int offset = len - 1 - idx;
return Hash2(h1.back().a + delta1.a * pw1[offset].a % MOD1,
h2.back().b + delta2.b * pw2[offset].b % MOD2);
}
};
字符串前后缀压缩
给定字符串列表，将相邻字符串中重叠的前后缀合并，例如：
输入：["sample", "please", "ease"]
输出："samplease"
算法核心：对每段待拼接字符串 s，尝试从其开头匹配当前结果字符串 res 的末尾最长公共前后缀。利用双哈希结构记录进度并累积Append部分即可。
std::string compress(std::vector<std::string>& inputs) {
std::string res = "";
std::vector<Hash2> prefix1{Hash2(1)}, prefix2{Hash2(1)};
for (const auto& str : inputs) {
if (str.empty()) continue;
int overlap = 0;
Hash2 cur1(0), cur2(0);
for (int i = 0; i < static_cast<int>(str.size()); i++) {
cur1 = cur1 * Hash2(BASE1) + Hash2(str[i]);
cur2 = cur2 * Hash2(BASE2) + Hash2(str[i]);
int match_len = i + 1;
if (match_len > static_cast<int>(res.size())) break;
Hash2 suf1 = prefix1.back() - prefix1[prefix1.size() - 1 - match_len] * pw1[match_len];
Hash2 suf2 = prefix2.back() - prefix2[prefix2.size() - 1 - match_len] * pw2[match_len];
if (suf1.a == cur1.a && suf1.b == cur1.b &&
suf2.a == cur2.a && suf2.b == cur2.b) {
overlap = match_len;
}
}
for (int i = overlap; i < static_cast<int>(str.size()); i++) {
res.push_back(str[i]);
prefix1.emplace_back(prefix1.back() * Hash2(BASE1) + Hash2(str[i]));
prefix2.emplace_back(prefix2.back() * Hash2(BASE2) + Hash2(str[i]));
}
}
return res;
}
应用示例：子串切割匹配
给定目标串 s 和模式串 x，找出一个分割点使得 s[l..r] + s[r+1..k] == x，即 x 是 s 中两个连续子串拼接的结果。
首先使用单哈希表征数值串（如仅含数字），再通过滑动窗口扫描所有可能的拼接位置：
int main() {
std::string s, x;
std::cin >> s >> x;
int n = s.size(), m = x.size();
long long MOD = find_prime(rng() % 900000000 + 100000000);
std::vector<long long> h(n + 1), p(n + 1);
p[0] = 1;
for (int i = 0; i < n; ++i) {
h[i + 1] = (10LL * h[i] + (s[i] - '0')) % MOD;
p[i + 1] = (10LL * p[i]) % MOD;
}
auto get_hash = [&](int l, int r) -> long long {
return (h[r] - h[l] * p[r - l] % MOD + MOD) % MOD;
};
long long tx = 0;
for (char c : x) tx = (10LL * tx + (c - '0')) % MOD;
// 情况一：两子串长度相等
for (int i = 0; i <= n - 2 * (m - 1); ++i) {
if ((get_hash(i, i + m - 1) + get_hash(i + m - 1, i + 2 * m - 2)) % MOD == tx) {
std::cout << i + 1 << " " << i + m - 1 << "\n";
std::cout << i + m << " " << i + 2 * m - 2 << "\n";
return 0;
}
}
// 情况二：KMP 提供前缀/后缀边界 sharper 剪枝
std::vector<int> z_func(m), fail(n);
// Z-algorithm for x
z_func[0] = m;
for (int i = 1, j = 0; i < m; ++i) {
if (j + z_func[j] > i) {
z_func[i] = std::min(z_func[i - j], j + z_func[j] - i);
}
while (i + z_func[i] < m && x[z_func[i]] == x[i + z_func[i]]) ++z_func[i];
if (j + z_func[j] < i + z_func[i]) j = i;
}
// Z-algorithm for matching x against s
for (int i = 0, j = 0; i < n; ++i) {
if (j + fail[j] > i && i < m) {
fail[i] = std::min(fail[i - j], j + fail[j] - i);
}
while (i + fail[i] < n && fail[i] < m && x[fail[i]] == s[i + fail[i]]) ++fail[i];
if (j + fail[j] < i + fail[i]) j = i;
}
// 枚举中间不匹配段，仅考虑局部修正
for (int i = 0; i + m <= n; ++i) {
int k = std::min(m, fail[i]);
for (int d : { m - k, m - k - 1 }) {
if (d <= 0) continue;
if (i >= d && (get_hash(i - d, i) + get_hash(i, i + m)) % MOD == tx) {
std::cout << i - d + 1 << " " << i << "\n";
std::cout << i + 1 << " " << i + m << "\n";
return 0;
}
if (i + m + d <= n && (get_hash(i, i + m) + get_hash(i + m, i + m + d)) % MOD == tx) {
std::cout << i + 1 << " " << i + m << "\n";
std::cout << i + m + 1 << " " << i + m + d << "\n";
return 0;
}
}
}
}
典例与复杂度要点
| 题号 | 类型 | 关键技术 | 复杂度 | 注意事项 |
|---|---|---|---|---|
| 1003F | 多字符串匹配计数 | 哈希 + KMP（定制化） | O(N²) | 需适配哈希数组而非原始字符串 |
| 7D | 回文判定 | 单哈希区间对称性 | O(N log N) | 双哈希可能 TLE |
| 25E | 三段拼接检查 | 暴力 + KMP | O(N³) | 注意避免 std::to_string 编码回文本 |
| 1200E | 后缀哈希 | 字典序比较 | O(N log N) | 常规哈希路径 |
| 514C | 改变一位匹配 | 字典树/哈希组合 | O(3·Σ | sᵢ |
此类题目常需根据数据规模选择合适哈希策略，当长度极长但序列较短时，应优先考虑哈希压缩后处理；若需频繁修改，应保留结构体支持 O(1) 修改；若涉及多维操作（如回文、前缀循环节），应结合其他线性预处理（Z 函数、KMP）增强剪枝能力。
