什么不属于网站推广软件,上海网站设计大连,搜索引擎优化名词解释,高端建设网站公司目录
一、首先使用拉链法#xff1a; 二、开放寻址法
三、字符串哈希
1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图
2.接下来说一说算某个中间的区间的字符串哈希值 哈希表是一种数组之间互相映射的数据结构#xff0c;比如举个简单的例子一个十个的数…目录
一、首先使用拉链法 二、开放寻址法
三、字符串哈希
1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图
2.接下来说一说算某个中间的区间的字符串哈希值 哈希表是一种数组之间互相映射的数据结构比如举个简单的例子一个十个的数组要用一个五个的数组表示我们可以使用取模的方法将十个数组中的数组映射到五个数字的小数组中。
核心思想是将数据项的键值Key通过哈希函数转换成数组的索引从而直接访问数组中的位置来存储或查找数据项。
但是一个大的数组映射到小的数组中是很难避免映射冲突的问题的为了解决这类问题我们常用两个方法来解决
拉链法开放寻址法
一、首先使用拉链法
拉链法顾名思义就是一个数组每个数组上链接一个单链表形状类似拉链故拉链。 但是如何取模运算是我们需要解决的问题。
听y总说寻找大于规定范围最小的质数是冲突最小我不知道为撒但是听说数学有证明
#includeiostream
#includecstring
using namespace std;int main()
{for(int i1e5;;i){bool flagtrue;for(int j 2 ; j * j i;j){if(i % j 0){flagfalse;break;}}if(flag){coutiendl;break;}}return 0;
} 例题https://www.acwing.com/activity/content/problem/content/890/
#includeiostream
#includecstring
using namespace std;
const int N1e53;
int h[N],e[N],ne[N],idx;void insert(int x)
{int k(x%NN)%N; //保证k的值不为负数e[idx]x;ne[idx]h[k];h[k]idx;idx;
}bool find(int x)
{int k(x%NN)%N; //保证k的值不为负数for(int ih[k];i!-1;ine[i]){if(e[i]x) return true;}return false;
}int main()
{int m;cinm;memset(h,-1,sizeof (h));while(m--){char op[2];int x;scanf(%s%d,op,x);if(*opI){insert(x);}else{if(find(x)) puts(Yes);elseputs(No);}}return 0;
} 二、开放寻址法
开放寻址法可以叫它为蹲坑法通常N要是数据范围的两倍然后找最小的大于数据范围的质数
然后在相应的地方进行插入数据。
#includeiostream
#includecstring
using namespace std;const int N200003,null0x3f3f3f3f;
int h[N];int find(int x)
{int k(x % N N) % N;while(h[k]!null h[k]!x){k;//到头就从头再来if(kN) k0;}return k;//保证k要么是空位置的地址要么是这个数已经被存放过了
}int main()
{int n;scanf(%d,n);memset(h,0x3f,sizeof h);while(n--){char op[2];int x;scanf(%s%d,op,x);if(*op I){h[find(x)] x;}else{if(h[find(x)] null) puts(No);else puts(Yes);}}return 0;
}
三、字符串哈希
一般常使用哈希来解决字符串的问题常用的方法就是将一个字符串差分成字符前缀然后存储每个字符前缀的哈希值然后这个哈希值常使用一种进制的表示方式来确定然后在进行取余。要点一般使用131进制取余的除数是而且使用unsigned long long 来存储也就可以通过溢出直接进行自动取余。
1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图 需要注意的是这里的哈希值的处理方式我们需要认为是不存在冲突的这一点和之前的数值哈希有所不同而且还要注意的是在映射的时候是不可以映射成为0的。
举个例子解释一下
如何某个字符前缀会映射成为0那比如说A是0那AB也就是0了这样是不符合要求的。
2.接下来说一说算某个中间的区间的字符串哈希值 如图所示最重要的公式就是
举个例子方便理解
我们在预处理h[i] 数组的时候,是把左边看成高位,右边看成低位(这与我们的习惯是相同的) 下面给出例子,计算[4,5]之间de 的哈希值 高位 a b c d e 低位 a b c 这是数组的下标 1 2 3 L R 这里是P进制下位权 (p^4) p^3 p^2 p^1 1 我们在前缀和那节课已经学过了,怎么计算区间的部分和. h[R] - h[L - 1]. 仔细一看,不对劲,位置对不上. 因此我们将字符串 左移,为他们补上位权,这样子就能做到一一对应 高位 a b c d e 低位 a b c \0 \0 这是数组的下标 1 2 3 L R 这里是P进制下位权 (p^4) p^3 p^2 p^1 1 为了方便理解,我用\0表示无意义字符. 这个时候就能计算了对吧? 那位移是多少呢? 就是 R - L 1,在本例中, 5 - 3 1 2,左移两位. 补齐低位. 例题https://www.acwing.com/activity/content/problem/content/891/
#includeiostream
using namespace std;const int N1e510,jinzhi131;unsigned long long h[N],p[N];//h是存放每个字符子串的哈希值p是存放字符串的权重的
char str[N];int get(int l,int r)
{return h[r]-h[l-1]*p[r-l1];
}int main()
{int n,m;scanf(%d%d,n,m);scanf(%s,str1);//初始化p[0]1;for(int i1;in;i){h[i]h[i-1]*jinzhistr[i];p[i]p[i-1]*jinzhi;}while(m--){int l1,l2,r1,r2;scanf(%d%d%d%d,l1,r1,l2,r2);if(get(l1,r1)get(l2,r2)){puts(Yes);}else puts(No);}return 0;
}
