51 · 字符串哈希与 Trie

字符串题只有两个基本动作：比较和查找。直接比较两个长 L 的串要 L 次字符比较；一万个长 1000 的串两两比较是 5×10¹⁰ 次，必然超时。这一节给两种把动作变便宜的工具：哈希把整个串压成一个整数，比较退化成一次整数比较；Trie 把公共前缀折叠成一条路径，插入和查询都只走 L 步。Trie 的一个变体把整数按二进制位建树，就能回答“和 x 异或最大的数是谁”。

先把这一节会出现的 4 样东西拆开。它们都很短，但每一件都有一个“不这么写就错”的细节，这四处细节才是真正的考点。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int main() {
    ull x = 0;
    --x;                              // 0 - 1 回绕到 2^64 - 1
    cout << x << "\n";                // 18446744073709551615

    string s = "abc";
    ull h = 0;
    for (char c : s) h = h * 131 + (ull)c;   // 等价于 (h * 131 + c) % 2^64
    cout << h << "\n";

    // 同一个函数对 "abc" 永远给出同一个数，这就是“指纹”
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll M1 = 1000000007, M2 = 1000000009;    // 两个不同的大质数
const ll B1 = 131,        B2 = 13331;        // 两套基数也要不同

pair<ll, ll> H(const string& s) {
    ll h1 = 0, h2 = 0;
    for (unsigned char c : s) {              // 转无符号，防止负字符
        h1 = (h1 * B1 + c) % M1;
        h2 = (h2 * B2 + c) % M2;
    }
    return {h1, h2};
}

int main() {
    vector<pair<ll, ll>> v = {H("abc"), H("abc"), H("abd")};
    sort(v.begin(), v.end());
    cout << unique(v.begin(), v.end()) - v.begin() << "\n";   // 2
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;                 // 节点上限 = 总字符数 + 1
int ch[MAXN][26], pass[MAXN], ended[MAXN], tot = 0;

void insert(const string& s) {
    int u = 0;                           // 从根出发
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) ch[u][x] = ++tot; // 边不存在才新建，这是“共享前缀”的全部秘密
        u = ch[u][x];
        ++pass[u];
    }
    ++ended[u];                          // 有一个串在这里结束
}

int node(const string& s) {              // 返回路径终点；-1 表示走不通
    int u = 0;
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) return -1;
        u = ch[u][x];
    }
    return u;
}
// node(s) != -1 → 以 s 为前缀的串有 pass[node(s)] 个
// ended[node(s)] > 0 → s 本身是一个插入过的串

const int MAXN = 100005;
int ch[MAXN * 31][2], tot = 0;

void insert(int x) {
    int u = 0;
    for (int b = 30; b >= 0; --b) {
        int c = (x >> b) & 1;
        if (!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
}

int query(int x) {                       // 与 x 异或的最大值
    int u = 0, r = 0;
    for (int b = 30; b >= 0; --b) {
        int c = (x >> b) & 1;
        if (ch[u][c ^ 1]) {              // 反边存在：这一位异或出 1
            r |= 1 << b;
            u = ch[u][c ^ 1];
        } else {                         // 只能将就，这一位异或出 0
            u = ch[u][c];
        }
    }
    return r;
}

读入 n
for 每个串 s:
    h = 0
    for c in s: h = h * 131 + c      # 溢出即 mod 2^64
    把 h 存进数组
排序、unique
输出 unique 之后的元素个数

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const ull B = 131;          // 基数：大于字符集(62)，且是质数

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

    int n;
    cin >> n;
    vector<ull> h;
    h.reserve(n);

    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        ull x = 0;
        // 每个串独立从 0 开始累；乘 131 后的溢出位被丢弃，正是 mod 2^64
        for (char c : s) x = x * B + (ull)c;
        h.push_back(x);
    }

    sort(h.begin(), h.end());              // 整数排序，比字符串比较便宜得多
    // unique 把不重复的元素挪到前面，返回新结尾；减去 begin 即个数
    cout << (int)(unique(h.begin(), h.end()) - h.begin()) << "\n";
    return 0;
}

哈希真正的威力不在“整串比较”，而在任意子串比较。要做到这一点，先算前缀哈希，再用一次减法把任意一段“抠”出来。

设 h[i] 是前 i 个字符的哈希，则 h[r] = h[l−1]·B^r−l+1 + H(l..r)：前 r 个字符 = 前 l−1 个字符整体左移 r−l+1 位，再接上第 l..r 个字符。移项得到子串哈希公式。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const ull B = 131;
const int MAXN = 1000005;
char s[MAXN];
ull h[MAXN], pw[MAXN];          // h：前缀哈希；pw：B 的幂

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

    cin >> (s + 1);             // 1 基下标，s[1] 是第一个字符
    int n = strlen(s + 1);

    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        h[i]  = h[i - 1] * B + (ull)s[i];   // 前 i 个字符的指纹
        pw[i] = pw[i - 1] * B;              // B^i
    }

    // 子串 [l, r]（1 ≤ l ≤ r ≤ n）的指纹
    auto sub = [&](int l, int r) -> ull {
        return h[r] - h[l - 1] * pw[r - l + 1];
    };

    int q;
    cin >> q;
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (sub(l1, r1) == sub(l2, r2) ? "Yes\n" : "No\n");
    }
    return 0;
}

这个公式是后面所有子串题的地基：找模式串出现位置（逐个起点比指纹）、最长公共前缀（二分长度 + 判等，O(log n)）、回文判断（正串和反串各一套哈希）。代价都是“预处理 O(n) + 每次询问 O(1) 或 O(log n)”。

哈希能判相等，却回答不了“有多少个串以某个前缀开头”——那是集合问题，不是相等问题。Trie 把公共前缀压成一条公共路径，走到某个节点，子树里有多少个词就是这个前缀的出现次数。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;               // 节点上限 = 所有串总长 + 1
int ch[MAXN][26], pass[MAXN], ended[MAXN], tot = 0;

void insert(const string& s) {
    int u = 0;                         // 根
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) ch[u][x] = ++tot;   // 没有这条边才新建：前缀只存一份
        u = ch[u][x];
        ++pass[u];                     // 经过 u 的串多了一个
    }
    ++ended[u];                        // 有一个串在这里结束
}

int node(const string& s) {            // 返回路径终点；-1 表示路断了
    int u = 0;
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) return -1;
        u = ch[u][x];
    }
    return u;
}

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

    int n, q;
    cin >> n >> q;
    string s;
    for (int i = 0; i < n; ++i) { cin >> s; insert(s); }

    while (q--) {
        cin >> s;
        int u = node(s);
        if (u == -1) { cout << "0 0\n"; continue; }
        cout << pass[u] << " " << (ended[u] > 0 ? 1 : 0) << "\n";
        // 第一个数：以 s 为前缀的串数；第二个数：s 自己是不是一个插入过的串
    }
    return 0;
}

把 Trie 的边从 26 条换成 2 条、从字符换成二进制位，就得到 01-Trie。它解决一类问题：给定一堆数，问“与 x 异或最大的数是谁”。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int ch[MAXN * 31][2], tot = 0;         // 每个数最多占 31 个节点

void insert(int x) {
    int u = 0;
    for (int b = 30; b >= 0; --b) {    // 从最高位开始，高位决定大小
        int c = (x >> b) & 1;
        if (!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
}

int query(int x) {                     // 返回与 x 异或能得到的最大值
    int u = 0, r = 0;
    for (int b = 30; b >= 0; --b) {
        int c = (x >> b) & 1;
        if (ch[u][c ^ 1]) {            // 反边存在 → 这一位异或出 1，必选
            r |= 1 << b;
            u = ch[u][c ^ 1];
        } else {
            u = ch[u][c];              // 没得选，这一位异或出 0
        }
    }
    return r;
}

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

    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (i > 1) ans = max(ans, query(x));   // 先问已有的数，答案一定来自两个不同的数
        insert(x);
    }
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;               // 节点上限 = n × 50
int ch[MAXN][26], ended[MAXN], tot = 0;
bool vis[MAXN];                        // 这个节点被点过名没有

void insert(const string& s) {
    int u = 0;
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) ch[u][x] = ++tot;   // 前缀只有一份
        u = ch[u][x];
    }
    ++ended[u];                        // 这个名字真的在名单里
}

int node(const string& s) {            // 返回终点编号；-1 表示路径不存在
    int u = 0;
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) return -1;
        u = ch[u][x];
    }
    return u;
}

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

    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; ++i) { cin >> s; insert(s); }

    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> s;
        int u = node(s);
        // 路走不通，或者走通了但这里没有名字结束：都不是名单里的名字
        if (u == -1 || ended[u] == 0) { cout << "WRONG\n"; continue; }
        if (vis[u]) { cout << "REPEAT\n"; continue; }
        vis[u] = true;
        cout << "OK\n";
    }
    return 0;
}