字符串哈希：用前缀值快速比较子串｜算法讲义

问题#

给定一个长度为 $n$ 的字符串和若干次询问。每次询问给出两个半开区间 $[l_1,r_1)$ 、 $[l_2,r_2)$ ，判断两个子串是否相同。

逐字符比较一次需要 $O(\text{子串长度})$ 。当字符串和询问都很大时，我们希望先做一次预处理，再用常数时间完成每次比较。

核心思想#

把字符串看成一个以常数 $B$ 为底的多项式。令字符编码为 $v_i$ ，定义前缀哈希：

H[i+1]=(H[i]\cdot B+v_i)\bmod M.

同时预处理 $P[k]=B^k\bmod M$ 。半开区间 $[l,r)$ 的哈希值为：

\operatorname{hash}(l,r) =H[r]-H[l]\cdot P[r-l]\pmod M.

这与前缀和相减很相似：乘上 $P[r-l]$ 是为了把左侧前缀移动到与 $H[r]$ 相同的位权。

不变量#

prefix[i] 始终表示前 $i$ 个字符，即区间 $[0,i)$ 的哈希。
power[i] 始终等于 $B^i\bmod M$ 。
同一套底数和模数下，相同字符串一定得到相同哈希；不同字符串则可能发生碰撞。

模板使用两组模数。两个子串只有在长度相同且两组哈希都相同时，才判为“哈希相同”。这能显著降低碰撞概率，但仍不是数学上的零碰撞保证。

课程主线说明：前缀哈希公式只需掌握一个模数；下面的双模版本只是把同一过程做两次以降低工程中的碰撞概率，属于“延伸阅读（非课程主线）”。保留双模代码是为了让模板默认更稳健，并不增加新的算法原理。

复杂度#

预处理时间： $O(n)$
预处理空间： $O(n)$
单次子串哈希与比较： $O(1)$

可独立编译的 C++17 模板#

输入约定：

第一行是字符串，可以为空。
第二行是询问数 $q$ 。
每次询问给出 l1 r1 l2 r2，均为 0-based 半开区间。

#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

class DoubleRollingHash {
public:
    using Hash = std::pair<std::uint64_t, std::uint64_t>;

    explicit DoubleRollingHash(const std::string& text)
        : size_(text.size()),
          power1_(size_ + 1, 1),
          power2_(size_ + 1, 1),
          prefix1_(size_ + 1, 0),
          prefix2_(size_ + 1, 0) {
        for (std::size_t i = 0; i < size_; ++i) {
            const std::uint64_t value =
                static_cast<unsigned char>(text[i]) + 1ULL;

            power1_[i + 1] = power1_[i] * kBase % kMod1;
            power2_[i + 1] = power2_[i] * kBase % kMod2;
            prefix1_[i + 1] =
                (prefix1_[i] * kBase + value) % kMod1;
            prefix2_[i + 1] =
                (prefix2_[i] * kBase + value) % kMod2;
        }
    }

    std::size_t size() const {
        return size_;
    }

    // 返回 text[l, r) 的双哈希。
    Hash slice(std::size_t l, std::size_t r) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid substring range");
        }

        const std::size_t length = r - l;
        const std::uint64_t left1 =
            prefix1_[l] * power1_[length] % kMod1;
        const std::uint64_t left2 =
            prefix2_[l] * power2_[length] % kMod2;

        const std::uint64_t hash1 =
            (prefix1_[r] + kMod1 - left1) % kMod1;
        const std::uint64_t hash2 =
            (prefix2_[r] + kMod2 - left2) % kMod2;
        return {hash1, hash2};
    }

    bool equal(
        std::size_t l1,
        std::size_t r1,
        std::size_t l2,
        std::size_t r2
    ) const {
        if (
            l1 > r1 || r1 > size_ ||
            l2 > r2 || r2 > size_
        ) {
            throw std::out_of_range("invalid substring range");
        }
        if (r1 - l1 != r2 - l2) {
            return false;
        }
        return slice(l1, r1) == slice(l2, r2);
    }

private:
    static constexpr std::uint64_t kBase = 911382323ULL;
    static constexpr std::uint64_t kMod1 = 1000000007ULL;
    static constexpr std::uint64_t kMod2 = 1000000009ULL;

    std::size_t size_;
    std::vector<std::uint64_t> power1_;
    std::vector<std::uint64_t> power2_;
    std::vector<std::uint64_t> prefix1_;
    std::vector<std::uint64_t> prefix2_;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string text;
    std::getline(std::cin, text);

    int query_count = 0;
    if (!(std::cin >> query_count)) {
        return 0;
    }

    const DoubleRollingHash hash(text);
    while (query_count-- > 0) {
        std::size_t l1 = 0;
        std::size_t r1 = 0;
        std::size_t l2 = 0;
        std::size_t r2 = 0;
        std::cin >> l1 >> r1 >> l2 >> r2;
        std::cout << (hash.equal(l1, r1, l2, r2) ? "Yes" : "No")
                  << '\n';
    }
}

示例#

输入：

abacaba
3
0 3 4 7
0 4 3 7
1 1 5 5

输出：

Yes
No
Yes

第一组比较的是两个 aba；第三组比较的是两个空子串。

易错点#

区间含义混乱：公式使用 $[l,r)$ ，长度是 $r-l$ ，不要再减一。
负数取模：C++ 的负数取模仍可能为负，先加模数再取模。
字符有符号性：直接把 char 转整数可能得到负数，模板先转为 unsigned char。
忘记比较长度：不同长度的字符串即使哈希偶然相同，也不能判等。
幂数组少一项：长度为 $n$ 的字符串需要下标 $0$ 到 $n$ 的幂。
把哈希当作绝对证明：双哈希只是把碰撞概率降得很低。需要确定性时，哈希命中后仍应直接比较原串。

边界测试#

空串、单字符、整个字符串和长度为 0 的子串。
匹配区间位于开头、结尾，以及两个区间发生重叠。
大量相同字符，例如 aaaaaaaa。
子串长度不同、内容不同但首尾字符相同。
随机生成短字符串和询问，与直接调用 string::compare 对拍。

变体#

单模哈希（课程主线）：只保留一组 power、prefix 和模数；代码更短，但碰撞风险高于正文的工程版。
回文判断：同时维护正向串与反向串的哈希。
最长公共前缀：对子串长度二分，并用哈希判断前缀是否相等。

问题#