字符串哈希与 哈希冲突处理

const unsigned long long B = 131;       // 也可以取 13331
unsigned long long h = 0;
for (int i = 0; i < s.size(); i++)
    h = h * B + (unsigned char)s[i];      // 自然溢出，等价于 mod 2^64

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1000005;
const ull B = 131;
ull pre[MAXN], pw[MAXN];       // pre[i] = 前 i 个字符的哈希, pw[i] = B^i

void build(const string& s) {
    int n = s.size();
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i]  = pw[i-1] * B;
        pre[i] = pre[i-1] * B + (unsigned char)s[i-1];
    }
}

ull getHash(int l, int r) {        // 1-based 闭区间 [l, r]
    return pre[r] - pre[l-1] * pw[r - l + 1];
}

// ① 线性探测
int h = hashi(k);
while (key[h] != EMPTY && key[h] != k) h = (h + 1) % M;

// ② 平方探测
for (int i = 0; i < M; i++) {
    int p = (hashi(k) + i * i) % M;
    if (key[p] == EMPTY || key[p] == k) { h = p; break; }
}

// ③ 链地址法（头插）
int hh = hashi(k);
val[++cntNode] = k;
nxt[cntNode] = head[hh];
head[hh] = cntNode;

// ④ 再哈希（双重散列）
int h2 = R - (k % R);              // R 是小于 M 的质数
for (int i = 0; i < M; i++) {
    int p = (hashi(k) + i * h2) % M;
    if (key[p] == EMPTY || key[p] == k) { h = p; break; }
}

// ⑤ 公共溢出区
int h0 = hashi(k);
if (key[h0] == EMPTY || key[h0] == k) key[h0] = k;
else overflow[++oTop] = k;         // 溢出表中线性查找

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

ull hashStr(const string& s) {
    ull h = 0;
    for (unsigned char c : s) h = h * B + c;   // 溢出即 mod 2^64
    return h;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    unordered_set<ull> S;
    for (int i = 0; i < n; i++) { string s; cin >> s; S.insert(hashStr(s)); }
    cout << S.size() << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const long long B = 131 % 1000000007LL;
const long long M = 1000000007LL;

long long hashStr(const string& s) {
    long long h = 0;
    for (unsigned char c : s) h = (h * B + c) % M;
    return h;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    unordered_set<long long> S;
    for (int i = 0; i < n; i++) { string s; cin >> s; S.insert(hashStr(s)); }
    cout << S.size() << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const long long B1 = 131,   M1 = 1000000007LL;
const long long B2 = 13331, M2 = 1000000009LL;

pair<long long,long long> hashStr(const string& s) {
    long long h1 = 0, h2 = 0;
    for (unsigned char c : s) {
        h1 = (h1 * B1 + c) % M1;
        h2 = (h2 * B2 + c) % M2;
    }
    return {h1, h2};
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    set<pair<long long,long long>> S;
    for (int i = 0; i < n; i++) { string s; cin >> s; S.insert(hashStr(s)); }
    cout << S.size() << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1000005;
const ull B = 131;
ull pre[MAXN], pw[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    int n = s.size();
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i]  = pw[i-1] * B;
        pre[i] = pre[i-1] * B + (unsigned char)s[i-1];
    }
    auto get = [&](int l, int r) -> ull {
        return pre[r] - pre[l-1] * pw[r - l + 1];
    };
    int q; cin >> q;
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (r1 - l1 != r2 - l2) { cout << "No" << "\n"; continue; }
        cout << (get(l1, r1) == get(l2, r2) ? "Yes" : "No") << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 100005;
const ull BASE = 131;               // 进制不要叫 B，避免与字符串变量重名
string A, T;
ull preA[MAXN], preB[MAXN], pw[MAXN];
int nA, nB;

void build(const string& s, ull pre[], int n) {
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i-1] * BASE + (unsigned char)s[i-1];
}
ull sub(ull pre[], int l, int r) {
    return pre[r] - pre[l-1] * pw[r - l + 1];
}

bool check(int len) {                    // 是否存在长度为 len 的公共子串
    if (len == 0) return true;
    unordered_set<ull> S;
    for (int i = 1; i + len - 1 <= nA; i++)
        S.insert(sub(preA, i, i + len - 1));
    for (int i = 1; i + len - 1 <= nB; i++)
        if (S.count(sub(preB, i, i + len - 1))) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> A >> T;
    nA = A.size(); nB = T.size();
    pw[0] = 1;
    for (int i = 1; i <= max(nA, nB); i++) pw[i] = pw[i-1] * BASE;
    build(A, preA, nA); build(T, preB, nB);
    int lo = 0, hi = min(nA, nB), ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1005;
const ull B = 131;
ull pre[MAXN], pw[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    int n = s.size();
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i]  = pw[i-1] * B;
        pre[i] = pre[i-1] * B + (unsigned char)s[i-1];
    }
    unordered_set<ull> S;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)
            S.insert(pre[r] - pre[l-1] * pw[r - l + 1]);
    cout << S.size() << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 100005;
const ull B = 131;
ull pre[MAXN], rpre[MAXN], pw[MAXN];
string s, rev;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> s;
    int n = s.size();
    rev = s; reverse(rev.begin(), rev.end());
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i]   = pw[i-1] * B;
        pre[i]  = pre[i-1]  * B + (unsigned char)s[i-1];
        rpre[i] = rpre[i-1] * B + (unsigned char)rev[i-1];
    }
    auto get = [&](ull pre[], int l, int r) -> ull {
        return pre[r] - pre[l-1] * pw[r - l + 1];
    };
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        // 原串 [l,r] ↔ 反串 [n-r+1, n-l+1]
        cout << (get(pre, l, r) == get(rpre, n - r + 1, n - l + 1) ? "Yes" : "No") << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 2000005;
const ull B = 131;
ull pre[MAXN], pw[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string A, Bs; cin >> A >> Bs;
    int n = A.size();
    if ((int)Bs.size() != n) { cout << "No" << endl; return 0; }
    string T = A + A;                 // 双串长度 2n
    pw[0] = 1;
    for (int i = 1; i <= 2 * n; i++) {
        pw[i]  = pw[i-1] * B;
        pre[i] = pre[i-1] * B + (unsigned char)T[i-1];
    }
    ull hb = 0;
    for (unsigned char c : Bs) hb = hb * B + c;
    for (int i = 1; i + n - 1 <= n + n; i++) {
        ull cur = pre[i + n - 1] - pre[i - 1] * pw[n];
        if (cur == hb) { cout << "Yes" << endl; return 0; }
    }
    cout << "No" << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const long long B1 = 131,   M1 = 1000000007LL;
const long long B2 = 13331, M2 = 1000000009LL;
long long p1[MAXN], p2[MAXN], h1[MAXN], h2[MAXN];

void build(const string& s) {
    int n = s.size();
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i++) {
        p1[i] = p1[i-1] * B1 % M1;
        p2[i] = p2[i-1] * B2 % M2;
        h1[i] = (h1[i-1] * B1 + (unsigned char)s[i-1]) % M1;
        h2[i] = (h2[i-1] * B2 + (unsigned char)s[i-1]) % M2;
    }
}

pair<long long,long long> sub(int l, int r) {
    long long v1 = ((h1[r] - h1[l-1] * p1[r-l+1]) % M1 + M1) % M1;
    long long v2 = ((h2[r] - h2[l-1] * p2[r-l+1]) % M2 + M2) % M2;
    return {v1, v2};
}

bool check(int len, int k) {
    if (len == 0) return true;
    vector<ull> v;
    for (int i = 1; i + len - 1 <= n; i++)
        v.push_back(pre[i+len-1] - pre[i-1] * pw[len]);
    sort(v.begin(), v.end());              // 排序后相同哈希相邻
    int run = 1;
    for (int i = 1; i < (int)v.size(); i++) {
        if (v[i] == v[i-1]) { if (++run >= k) return true; }
        else run = 1;
    }
    return false;
}

struct Node { ull h; int len; };
Node merge(const Node& L, const Node& R) {
    return { L.h * pw[R.len] + R.h, L.len + R.len };
}
// 单点修改：把叶子节点的字符更新，再一路向上 merge
// 区间查询：合并路径上所有被覆盖的节点（注意按左右顺序合并）

bool eraseVal(long long x) {
    int h = hashi(x);
    int prev = 0;                      // 前驱节点编号，0 表示表头
    for (int i = head[h]; i; i = nxt[i]) {
        if (val[i] == x) {
            if (prev == 0) head[h] = nxt[i];   // 删的是表头
            else nxt[prev] = nxt[i];            // 跳过当前节点
            return true;
        }
        prev = i;
    }
    return false;
}