acm基础|哈希has散列-字符串hash 字符串|c++基础

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

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

现在要进行N次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数N，表示操作数量。
【acm基础|哈希has散列-字符串hash】接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。
输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤N≤1051≤N≤105
?109≤x≤109?109≤x≤109
输入样例：

5 I 1 I 2 I 3 Q 2 Q 5

输出样例：

Yes No

#include #include #include #include #include #include #include #include using namespace std; const int N=100003; int n; int h[N],e[N],ne[N],idx; void insert(int x){ intk=(x%N+N)%N; e[idx]=x; ne[idx]=h[k]; h[k]=idx++; }intfind(int x){ int k=(x%N+N)%N; int t=h[k]; while(t!=-1){ if(e[t]==x) return 1; t=ne[t]; } return 0; } int main(){ scanf("%d",&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(find(x)) printf("Yes\n"); else printf("No\n"); } } return 0; }

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2l1,r1,l2,r2，请你判断[l1,r1l1,r1]和[l2,r2l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数n和m，表示字符串长度和询问次数。
第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。
接下来m行，每行包含四个整数l1,r1,l2,r2l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从1开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：

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

输出样例：

Yes No Yes

#include #include #include #include #include #include #include #include using namespace std; const int N=100010,P=1331; typedef unsigned long long ULL; int n,m; ULL h[N],p[N]; char str[N]; int ha(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; }int main(){ p[0]=1; scanf("%d%d",&n,&m); scanf("%s",str+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 l,r,L,R; scanf("%d%d%d%d",&l,&r,&L,&R); if(ha(l,r)==ha(L,R)) printf("Yes\n"); else printf("No\n"); } return 0; }