哈希表

模拟散列表

维护一个集合，支持如下几种操作：

1. I x，插入一个数 x；
2. Q x，询问数 x是否在集合中出现过；

现在要进行 N次操作，对于每个询问操作输出对应的结果。

开放寻址法

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 200003, null = 0x3f3f3f3f;
int h[maxn];
int find(int x)
{
    int t = (x % maxn + maxn) % maxn;
    while (h[t] != null && h[t] != x)
    {
        t++;
        if (t == maxn) t = 0;
    }
    return t;
}
int main()
{
    memset(h, 0x3f, sizeof h);
    int n;
    cin >> n;
    while (n--)
    {
        char op[2];
        int x;
        cin >> op >> x;
        if (*op == 'I')
        {
            h[find(x)] = x;
        }
        else
        {
            if (h[find(x)] == null) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
    return 0;
}

拉链法

#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 100003;
int h[maxn], e[maxn], ne[maxn], idx;
void insert(int x)
{
    int k = (x % maxn + maxn) % maxn;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}
bool find(int x)
{
    int k = (x % maxn + maxn) % maxn;
    for (int i = h[k]; i != -1; i = ne[i])
    {
        if (e[i] == x)
        {
            return true;
        }
    }
    return false;
}
int main()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    while (n--)
    {
        char op[2];
        int x;
        cin >> op >> x;
        if (*op == 'I')
        {
            insert(x);
        }
        else
        {
            if (find(x)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}

字符串哈希

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int N = 100010, 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 >> n >> m;
    cin >> (str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    while (m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) 
            cout << "Yes" << endl;
        else 
            cout << "No" << endl;
    }
    return 0;
}