知识点
字符串前缀哈希法
- 把字符串看成一个p进制的数,字符串有几位,看成有几位
- 把p进制的数转化为10进制的数
- 把10进制的数mod上一个Q
把字符串转化为10进制并mod上Q,这样就可以把任何一个字符串映射到1~Q的数
注意
- 不能映射成0
- 不考虑冲突
- p = 131或者13331,Q = 2^64,基本上不会出现冲突
前缀和公式:h[i - 1] * p + str[i]
区间和公式:h[l,r]=h[r]−h[l−1]×P^r−l+1
用途:可以快速判断把一个字符串中的两个子串相不相同
Java代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static long[] h = new long[N]; //h[]存储前n个字符串的哈希值
static long[] p = new long[N]; //p[k]存储P^k % 2^64 溢出等价于对2 ^ 64取模
static int P = 131; //P代表131进制
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
String s = " " + in.next(); //因为没有空格,所以读取的是一整行字符串;因为是从1开始的,用前面的空格代替一个字符
char[] str = s.toCharArray();
p[0] = 1; //P的零次方 = 1;
for(int i = 1; i <= n; i ++)
{
h[i] = h[i - 1] * P + str[i]; //前缀和数组
p[i] = p[i - 1] * P;
}
while(m-- > 0)
{
int l1 = in.nextInt();
int r1 = in.nextInt();
int l2 = in.nextInt();
int r2 = in.nextInt();
if(get(l1,r1) == get(l2,r2)) System.out.println("Yes");
else System.out.println("No");
}
}
private static long get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1]; //区间和公式,乘以p[]是为了把高位对齐
}
}