Hash表也叫散列表
我们可以利用Hash表来比较字符串是否相等
如果一个个字符进行比较,时间复杂度就为O(n)
所以,把每个字符或字符串映射成一个整数来进行比较这些整数是否相等,这样时间复杂度就为O(1)。
这个映射函数叫做hash函数,存放记录的数组叫做hash表。
例如:a我们可以表示为1,b就为2....abc就是123.比较abc和abc就是看123是否等于123....26个字符就是:a-z(1-26).
为了尽可能不重复,我们把各字符映射成的整数然后存在hash表里的数都弄成131或13331进制的数(以下以131为主)
hash(a)=1
hash(ab)=1131+2=133//乘131表示移位,让一位来存上2
hash(abc)=1131^2+2*131+3=17426
abc如果要跟另外一个字符比较,只要比较那个字符的hash值是否为17426即可。
在unsigned long long中溢出就表示模了2的64次方,所以hash表的类型应该用unsigned long long
如何算出h[r]到h[l]之间的字符串的值呢?
如图:
(画的丑不要喷QAQ)
红笔表示把h[l-1]这些跟移到另外那里。
所以在弄个p[]数组,存下131的各个次方。
再结合图就可得出:h[l到r]=h[r]-h[l-1]*p[r-l+1]
看题:
题目描述
很久很久以前,森林里住着一群兔子。有一天,兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列(小兔子是外星生物,DNA 序列可能包含 26 个小写英文字母),然后我们每次选择两个区间,询问如果用两个区间里的 DNA 序列分别生产出来两只兔子,这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
输入描述:
第一行一个 DNA 字符串 S。
接下来一个数字 m,表示 m 次询问。
接下来 m 行,每行四个数字 l1, r1, l2, r2,分别表示此次询问的两个区间,注意字符串的位置从1开始编号。
其中 1 \leq length(S)1≤length(S),m \leq 1000000m≤1000000
输出描述:
对于每次询问,输出一行表示结果。如果两只兔子完全相同输出 Yes,否则输出 No(注意大小写)
实际上就是比较两个区间是否相同
代码:
#include <iostream> #include <string.h> using namespace std; typedef unsigned long long ULL; const int N = 1000010, base = 131; char s[N]; ULL p[N], h[N];//p进制数和hash ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { scanf("%s", s + 1); int n = strlen(s + 1); p[0] = 1;//p的0次方为1 for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * base + s[i] - 'a' + 1; p[i] = p[i - 1] * base; } int m; scanf("%d",&m); 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; }