题目描述

将字符串看作是一个P进制的数，其每一位都是P进制下的一位数字，对于数字串str = 12345678来说他是P进制，我们令前缀
hash[1] = 1;
hash[2] = 12;
hash[3] = 123;
…
hash[8] = 12345678;
如果我们想要计算s[2, 3]的值也就是求出来23，就有下面计算方式(hash取值)：
hash[3] - hash[1] * 10^2 = 123 - 1 * 100 = 23（也就是将百位去掉）
代入到字符串中来说，为P进制求字符串的s[l, r]就是：
hash[r] - hash[l - 1] * P^(r - l + 1),这就是这一段的字符串哈希值

对于P的幂和hash的构造

//exp[i]为p^i
exp[0] = 1; //p^0 = 1;
for (int i = 1; i <= n; i++) {
    exp[i] = exp[i - 1] * p;
    hash[i] = hash[i - 1] * p + (对于str第i位字符的映射(看情况但不要为0))
}

判断子串是否相等(直接判断hash即可)

static int getHash(int l, int r) {
    return hash[r] - hash[l - 1] * exp[r - l + 1];
}

注

1.并非完全正确代码，需考虑类型转换

2.在过程中可以添加对于大质数的取模操作(根据同余的性质)

3.P一般取131, 13331，这取决于字符的种类等，mod取(2^64) - 1

完整代码

import java.util.*;

public class Main {
    static final int N = 100010, p = 131, mod = (int)1e9 + 7;
    static int[] exp = new int[N], hash = new int[N];
    static int n, q;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();
        String str = sc.next();

        exp[0] = 1;
        for (int i = 1; i <= n; i++) {
            exp[i] = (int)((long)exp[i - 1] * p % mod);
            hash[i] = (int)(((long)hash[i - 1] * p + str.charAt(i - 1) - 'a' + 1) % mod);//加一做一个偏移量
        }

        while (q -- > 0) {
            int l1 = sc.nextInt(), r1 = sc.nextInt(), l2 = sc.nextInt(), r2 = sc.nextInt();
            if (getHash(l1, r1) == getHash(l2, r2)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }

    static int getHash(int l, int r) {
        return (int) (((hash[r] - (long)hash[l - 1] * exp[r - l + 1]) % mod + mod) % mod);
    }
}

哈希碰撞解决方案之多哈希检查

import java.util.*;

public class Main {
    static  final int N = 200010;
    static  int[] p = new int[]{131, 13331, 127};
    static int[] mod = new int[]{998244353, 1000000007, 12323};
    static long[][] exp  = new long[3][N], hash = new long[3][N];
    static int n, q;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();
        String str = sc.next();

        for (int i = 0; i < 3; i++) {
            exp[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                exp[i][j] = exp[i][j - 1] * p[i] % mod[i];
                hash[i][j] = (hash[i][j - 1] * p[i] + str.charAt(j - 1) - '0') % mod[i];
            }
        }

        while (q -- > 0) {
            int l1 = sc.nextInt(), r1 = sc.nextInt(), l2 = sc.nextInt(), r2 = sc.nextInt();
            if (check(l1, r1, l2, r2))
                    System.out.println("Yes");
            else
                System.out.println("No");
        }
    }

    public static boolean check(int l1, int r1, int l2, int r2) {
        for (int i = 0; i < 3; i++) {
            if (getHash(i, l1, r1) != getHash(i, l2, r2))
                return false;
        }
        return true;
    }

    public static long getHash(int i, int l, int r) {
        return (hash[i][r] - hash[i][l - 1] * exp[i][r - l + 1] % mod[i] + mod[i]) % mod[i];
    }
}