存储结构:
1.开放寻址法
#include<cstring>
#include <iostream>
using namespace std;
const int N=2000003, null = 0x3f3f3f3f;
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; //如果k在哈希表当中k就是下标;如果k不在哈希表当中,k就是应该存储的位置。
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin>>n;
memset(h,0x3f,sizeof h);
while(n--)
{
char op[2];
int x;
cin>>op>>x;
int k = find(x);
if(op[0]=='I')
{
h[k] = x;
}
else
{
if(h[k]!=null) puts("Yes");
else puts("No");
}
}
return 0;
}
2.拉链法
c++中的memset使用方法-->http://t.csdnimg.cn/XzqDc
#include<cstring>
#include <iostream>
using namespace std;
const int N=1000003;
int h[N], e[N], ne[N], idx;
int n;
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()
{
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin>>n;
memset(h,-1,sizeof h);
while(n--)
{
char op[2];
int x;
cin>>op>>x;
if(op[0]=='I') insert(x);
else
{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
字符串哈希方式:很多需要KMP的方法都可以用字符串哈希
作用:快速判断两个字符串是否相等
#include <iostream>
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()
{
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
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;
}
标签:return,puts,记录,int,cin,表自,哈希,NULL,op
From: https://blog.csdn.net/liu285783/article/details/137499176