• 预处理前缀 h(i) = h(i-1) * p + str[i]

与整数离散化的区别

整数离散化需要保序，而且不会发生冲突，每一个元素都有唯一确定的位置（1 ~ n）

840 ?拉链法

840. 模拟散列表 - AcWing题库

h 数组维护 N 条链，空节点表示-1，e 数组与 ne 数组维护链上的每一个节点，idx为每个节点分配唯一标识符；插入操作从链表头结点插入

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 质数

int h[N], e[N], ne[N], idx;

void insert(int x) {
    // 第一次模余数可能是负数，第二次模余数绝对是正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x) return true;

    return false;
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    while (n--) {
        string s;
        int x;
        cin >> s >> x;
        if (s == "I")
            insert(x);
        else {
            if (find(x))
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

840 ?开放寻址法

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 2e5 + 3, null = 0x3f3f3f3f;  // 质数

int h[N];

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k++;
        if (k == N) k = 0;  // 查到数组最后从开头找
    }
    return k;
}

int main() {
    cin.tie(0);
    memset(h, 0x3f, sizeof h);
    int n;
    cin >> n;
    while (n--) {
        string s;
        int x;
        cin >> s >> x;
        int k = find(x);
        if (s == "I")
            h[k] = x;
        else {
            if (h[k] != null)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

841 ?? 字符串哈希

841. 字符串哈希 - AcWing题库

如下的朴素算法会超时

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    cin.tie(0);
    string s;
    int n, m, l1, l2, r1, r2;
    cin >> n >> m >> s;
    while (m--) {
        cin >> l1 >> r1 >> l2 >> r2;
        l1 -= 1, l2 -= 1, r1 -= 1, r2 -= 1;
        if (s.substr(l1, r1 - l1 + 1) == s.substr(l2, r2 - l2 + 1))
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}

p 数组提前存储预处理的 p 次方的值，减少计算量

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

int main() {
    cin.tie(0);
    cin >> n >> m >> str + 1;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }

    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

STL

size()、empty() 所有容器都有，时间复杂度 \(O(1)\)

clear() 并不是所有容器都有，队列、优先队列、栈；范围遍历可以遍历所有容器

? 系统为某一个程序分配空间时，所需的时间与空间大小无关，与申请次数有关

vector

变长数组，倍增，支持比较运算（字典序（4个3小于3个4））。有erase但用得不多

插入操作\(O(1)\)：插入1e6次，申请空间的次数 \(log_21e6\) ，拷贝的次数均摊是 1 （数组大小从1到1e6，总共拷贝次数是1e6（1+2+4+8+...））

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // ^ 定义一个长度为10的vector，每个数都是3
    vector<int> a(10, 3);
    vector<int> b[10];

    a.push_back(1);

    cout << a.size() << endl;
    cout << a.empty() << endl;
    a.clear();
    cout << a.front() << endl;
    cout << a.back() << endl;
    // a.begin(); // ^ 返回的是迭代器（指针），需要解引用
    // a.end();
    return 0;
}

pair

二元组，支持比较运算（字典序）。适用于某种东西有两个属性，也可以存储三个属性，任意嵌套

相比结构体：pair 帮我们实现了结构体，并实现了比较函数，省了点代码