字符串哈希
预备知识题目算法分析关键变量源代码关键代码分析
预备知识
对溢出机制的理解: 什么是溢出?就是如果计算机只想要后8位,而我们目前拿到的数据是16位,那么只会保留后八位,而会使前八位溢出,如果用数学表达式来说明: 16位数据为 x 移除后数据为 y 则: y=x%28 记忆方式就是保留几位就对2的几次幂取模 原理: 以保留后八位为例,从第九位开始以后,每一位都是28的倍数,因此做模28会去除所有28的倍数,留下小于28的数,也就是前8位了(前八位表示的最大的数也不会大于28)
题目
给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。 字符串中只包含大小写英文字母和数字。
输入格式 第一行包含整数n和m，表示字符串长度和询问次数。 第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。 接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。 注意，字符串的位置从1开始编号。
输出格式 对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。 每个结果占一行。 数据范围 1≤n,m≤105
输入样例： 8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2
输出样例： Yes No Yes
算法分析
字符串哈希的本质上,是把每一个字符串看做一个p进制的数,并对这个数取模运算,因为我们取经验值p=131,模取264,因此可以认为每一个字符串都有独特的值, 通过前缀字符串,经过位运算可以求出任意子字符串的取值,当然这个也是唯一的,比较即可.
关键变量
s[]:前缀字符串哈希值数组p1[]:保存幂值的数组(方便调用)p:进制数,经验为131或13331
源代码
import java
.util
.Scanner
;
class Main{
static int N
=100010;
static long[] s
=new long[N
];
static long[] p1
=new long[N
];
public static void main(String
[] args
){
p1
[0]=1;
int p
=131;
Scanner sc
=new Scanner(System
.in
);
int n
=sc
.nextInt();
int m
=sc
.nextInt();
char[] c
=new char[N
];
sc
.nextLine();
String s1
=sc
.nextLine();
for(int i
=0;i
<n
;i
++){
c
[i
+1]=s1
.charAt(i
);
}
for(int i
=1;i
<=n
;i
++){
p1
[i
]=p1
[i
-1]*p
;
s
[i
]=s
[i
-1]*p
+c
[i
];
}
while(m
-->0){
int l1
=sc
.nextInt();
int r1
=sc
.nextInt();
int l2
=sc
.nextInt();
int r2
=sc
.nextInt();
long res1
=hash(l1
,r1
);
long res2
=hash(l2
,r2
);
if(res1
==res2
) System
.out
.println("Yes");
else System
.out
.println("No");
}
}
public static long hash(int l
,int r
){
return s
[r
]-s
[l
-1]*p1
[r
-l
+1];
}
}
关键代码分析
如何求任何子串的hash值? 首先确定对于字符串来说,右边是低位,左边是高位. 为了求出子串的哈希值,只需要将前l-1位左移(低位补0)至r位,相比r的前缀得到的就是目标位置为0的哈希值,这时候只需要让 s[r]-s[移位后],差值就是所求p数组就是单纯的求p的n次幂,好处就是方便使用了,所以在求前缀的时候顺手求出
