JAVA实现字符串哈希

实现字符串哈希的注意点
（1）java没有c++中unsigned long long类型，但是Long.MAX_VALUE就足够了
（2）本题字符串哈希下标是从1开始的，处理的时候需要注意数组下标
（3）解释：
p数组用来预处理p的次幂，h数组用来存前i项的哈希函数值。
字符串哈希的基本原理

AC代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int MAXN = (int)(1e6 + 100);
    static long[]p = new long[MAXN];
    static long[]h = new long[MAXN];
    static int P = 13331;
    static int n = 0;
    static long M = Long.MAX_VALUE;  //越大越好
    public static void main(String[] args) throws Exception {
        String nm[] = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        String str = br.readLine();
        char s[] = str.toCharArray(); //字符串转字符数组
        p[0] = 1;
        h[0] = 0;
        for(int i = 0; i < n; i++) {
            p[i + 1] = p[i] * P; //预处理p的次幂
            h[i + 1]  = h[i] * P + s[i]; //求前i项的哈希函数值
        }
        while((m--) > 0) {
            String lr[] = br.readLine().split(" ");
            int l1 = Integer.parseInt(lr[0]);
            int r1 = Integer.parseInt(lr[1]);
            int l2 = Integer.parseInt(lr[2]);
            int r2 = Integer.parseInt(lr[3]);
            if(substr(l1,r1,l2,r2)) {
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }


    }
    //查询区间
    static long get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    //判断子串是否相同
    static boolean substr(int l1,int r1,int l2,int r2) {
        return get(l1,r1) == get(l2,r2);
    }
}