字符串哈希

算法思想

1. 使用散列表将字符串映射为数字
2. 根据映射结果判断是否相同

子串哈希值

• 为每个子串生成一个哈希值

如何计算指定子串的哈希值

• 指定子串 a 为区间[l, r]上的字符串联得出的字符串
• 如何计算该子串的哈希值

已知 h[l - 1], h[r] 和进制数 P,
则子串哈希值为 h[r] - h[l - 1] * P ^ (r - l + 1)。

h[l - 1] * P ^ (r - l + 1)，即为 h[l] 左移 r - l + 1位

类似于，
求解二进制数1111 1111第7~8位上的数（从左到右）
h[6] = 1111 11
h[8] = 1111 1111
temp = h[6] * 2 ^ (8 - 7 + 1) = 1111 1100
result = 11
  1111 1111 
- 1111 1100
------------
         11

算法模板

import java.util.*;
import java.io.*;

public class Main {
    static int N = 100010;
    // 此处采用 P 进制
    // 选择131 或 13331 作为进制数，可以避免哈希碰撞
    static int P = 131;
    // p[k]存储 P^k mod 2^64
    static long[] p = new long[N];
    // h[k]存储字符串前 k 个字符的哈希值
    // 最大哈希值为 2e64 - 1
    static long[] h = new long[N];


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        var pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        var str = in.next();
        char[] chars = new char[N];
        
        for(int i = 1; i <= n; i ++ ) chars[i] = str.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 + chars[i];
        }
        
        while(m -- > 0)
        {
            int l1 = in.nextInt(), r1 = in.nextInt();
            int l2 = in.nextInt(), r2 = in.nextInt();
            String res = get(l1, r1) == get(l2, r2) ? "Yes" : "No";
            pw.println(res);
        }
        pw.flush();
    }
    
    // 计算子串 s[l ~ r] 的哈希值
    static long get(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
}