模拟散列表

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

“I x”，插入一个数x；
“Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数N，表示操作数量。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。

输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤N≤10^5
−109≤x≤10^9

输入样例

5
I 1
I 2
I 3
Q 2
Q 5

输出样例

Yes
No

拉链法

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 100003;//最好是一个质数
int e[N], ne[N], h[N], idx;
int n;

void insert(int x)//插入操作
{
    int k = (x % N + N) % N;//保证k是正数
    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 >> n;
    memset(h, -1, sizeof h);//初始化
    while (n--)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (op[0] == 'I')
            insert(x);
        else if (op[0] == 'Q')
        {
            if (find(x))
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

开放寻址法

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 200003,null=0x3f3f3f3f;//经验值:数据范围的2倍,并且最好是一个质数
int h[N];
int 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 >> n;
    memset(h, 0x3f, sizeof h);//初始化
    while (n--) 
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int loc = find(x);
        if (op[0] == 'I')
            h[loc] = x;
        else if (op[0] == 'Q')
        {
            if (h[loc]!=null)//当前位置为空就不存在
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

字符串哈希

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数n和m，表示字符串长度和询问次数。

第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。

接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从1开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤n,m≤10^5

输入样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例

Yes
No
Yes

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;

typedef  unsigned long long ULL;
const int N = 1e5+10,P=131;//经验值:P取131或13331
int h[N],p[N];//h表示哈希值,p表示P的p-1次幂
int n, m;
char str[N];

ULL get(int l,int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];//l到r区间内字符串的哈希值
}

int main()
{
    scanf("%d%d%s", &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];//将字符串转换为P进制的数
    }
    while (m--) 
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}