字符串哈希
简单说就是把一个字符串映射成一个p进制的数字,每一个字符代表一位
举个例子,就是把一个字符串如”abc”映射成一个p进制的数字
“abc” –> p^2+a + p^1+b + p^0+c = 哈希值
一般p取131或13331,别问,问就是y总说的
本题需要求到一个字符串中任意两个区间的子串是否相同
即为求两个区间子串的哈希值是否相等
unsigned long long 和java——long
-
首先,大家需要明确一个概念,java的long 是四字节32位,而c的long是2字节32位,longlong是2字节64位
也就是说,java中的long和c中long long 是一样的 -
java中的long 的数组范围是 -4^32 –4^32-1 ,unsigned 的范围是 0——2^64-1,即这个数据类型表示的数据的多少是一样的 ,都是 2^64个
- 而且java中long也有溢出操作,有兴趣的可以试一下 Long.MAX_VALUE+2的值
-
而之所以取模是为两个数字不一样就代表着字符串不一样,既然如此不用看值,只需要直到有2^64个不一样的数字(或者标记)来进行比较就行了,正负已经无所谓了,只需要表示的标记不同即可
-
所以,java可以用直接用long来写
但是java改成int也对
这个我不知道为什么了,可能是数据的问题,有没有大佬用c试一下,开int ,
看一下结果,我感觉也是对的
long
import java.util.Scanner;
public class Main {
static int N=100010;
static long p[]=new long [N];
static long h[]=new long [N];
static char c[]=new char [N];
static long P=131;//或者13331
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
String s=sc.next();
//进行边界处理
// for (int i = 0; i <n; i++) {
// p[i]=i==0?P:p[i-1]*P;
// h[i]=i==0?c[i]:h[i-1]*P+c[i];
// }
//或者把字符串往后延伸一位,不用处理边界了
for (int i = 1; i <=n; i++) {
c[i]=s.charAt(i-1);
}
p[0]=1;
for (int i = 1; i <=n; i++) {
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+c[i];
}
while(m--!=0) {
int l1=sc.nextInt();
int r1=sc.nextInt();
int l2=sc.nextInt();
int r2=sc.nextInt();
if(check(l1,r1,l2,r2)) System.out.println("Yes");
else System.out.println("No");
}
}
private static boolean check(int l1, int r1, int l2, int r2) {
return h[r1]-h[l1-1]*p[r1-(l1-1)]== h[r2]-h[l2-1]*p[r2-(l2-1)];
//前缀和
}
}
改int
import java.util.Scanner;
public class Main {
static int N=100010;
static int p[]=new int [N];
static int h[]=new int [N];
static char c[]=new char [N];
static int P=131;//或者13331
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
String s=sc.next();
//进行边界处理
// for (int i = 0; i <n; i++) {
// p[i]=i==0?P:p[i-1]*P;
// h[i]=i==0?c[i]:h[i-1]*P+c[i];
// }
//或者把字符串往后延伸一位,不用处理边界了
for (int i = 1; i <=n; i++) {
c[i]=s.charAt(i-1);
}
p[0]=1;
for (int i = 1; i <=n; i++) {
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+c[i];
}
while(m--!=0) {
int l1=sc.nextInt();
int r1=sc.nextInt();
int l2=sc.nextInt();
int r2=sc.nextInt();
if(check(l1,r1,l2,r2)) System.out.println("Yes");
else System.out.println("No");
}
}
private static boolean check(int l1, int r1, int l2, int r2) {
return h[r1]-h[l1-1]*p[r1-(l1-1)]== h[r2]-h[l2-1]*p[r2-(l2-1)];
//前缀和
}
}