方法

字符串前缀哈希法，预处理字符串所有前缀的哈希值

实现

  1. str = "abcABCzdkk";
  3. h[0] = 0;
  4. h[1] = hash("a");
  5. h[2] = hash("ab");
  6. h[3] = hash("abc");
  7. ...

**hash()** 函数如何实现？
将字符串看成是P进制数，转换成数字后对Q取余
P一般取131 或 13331或99901。

我想131是应为方便处理ASCII字符集，而13331可能是为了处理部分Unicode字符集吧

Q一般取2``64或1713302033171

避免冲突

  1. str = "abcABCzdkk";
  2. //假设P取131
  3. h[0] = 0;
  4. h[1] = (0 * 131 + 'a') % 2^64;
  5. h[2] = (h[1] * 131 + 'b') % 2^64;
  6. h[3] = (h[2] * 131 + 'c') % 2^64;
  7. ...

对于字符串中字符的要求：不能出现 '\0' ，如果出现的话， '\0' 和 '\0\0' 会被认作是相同的字符串，这显然不行。

冲突问题：
有没有可能发生冲突，即某两个字符串的经过哈希后结果相同？
答：有可能，但发生的概率极小，因为Q取2^64

java如何取模

利用long类型，正好是8字节64位，因为运算只包括加减乘，不包括除法，所以符号位对运算的结果没有影响。可以看成是无符号类型。
取模正好用截断来进行处理

除法需要考虑符号。比如4位二进制的计算，给定1000，如果我们当作无符号整数计算的话除以2应该是0100，但是按照有符号的补码计算的结果是1100，因为补码除法在运算前需要检测符号位，进行预处理

加减乘都是在补码的情况下进行计算，举个例子： Integer.MAX_VALUE + 2 结果的二进制形式为 10000000000000000000000000000001 打印结果为负数是因为int是有符号类型，最高位被看成了符号位。

image.png

作用

  1. 判断两个字符串是否相同
  2. 给定字符串和字符串中的两段子串，问两段子串是否相同

在构建好字符串哈希后，上述问题的时间复杂度都为O(1)

例题

841. 字符串哈希

给定一个长度为 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
输入样例：

  1. 8 3
  2. aabbaabb
  3. 1 3 5 7
  4. 1 3 6 8
  5. 1 2 1 2

输出样例：

  1. Yes
  2. No
  3. Yes
  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static final int N = 100010, P = 131;
  6.     static long[] h = new long[N], p = new long[N];
  9.     public static void main(String[] sss) throws IOException{
  10.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  11.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  13.         String[] str = br.readLine().split(" ");
  14.         int n = Integer.parseInt(str[0]);
  15.         int m = Integer.parseInt(str[1]);
  16.         String s = br.readLine();
  18.         p[0] = 1;
  19.         for (int i = 1; i <= n; i++) {
  20.             p[i] = p[i-1] * P;
  21.             h[i] = h[i-1] * P + s.charAt(i - 1);
  22.         }
  24.         while (m-- > 0) {
  25.             str = br.readLine().split(" ");
  26.             int l1, r1, l2, r2;
  27.             l1 = Integer.parseInt(str[0]);
  28.             r1 = Integer.parseInt(str[1]);
  29.             l2 = Integer.parseInt(str[2]);
  30.             r2 = Integer.parseInt(str[3]);
  32.             if (get(l1, r1) != get(l2, r2)) bw.write("No\n");
  33.             else bw.write("Yes\n");
  34.         }
  37.         br.close();
  38.         bw.close();
  40.     }
  42.     //注意这里计算[l,r]子串的哈希采用的是类似前缀和的操作
  43.     static long get(int l, int r) {
  44.         return h[r] - h[l - 1] * p[r - l + 1];
  45.     }
  46. }

求子串哈希.pdf