18502 字符串哈希匹配字符串

18502 字符串哈希匹配字符串

⭐️难度：中等
🌟考点：字符串hash
📖

📚

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int MOD = 1000000007;
    static int p = 131;

    static long[] b = new long[200005];
    static long[] h = new long[200005];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();

        String str = " " + sc.next();

        // hash
        b[0] = 1;
        for (int i = 1; i <= n; i++) {
            b[i] = b[i - 1] * p % MOD;
            h[i] = (h[i - 1] * p + str.charAt(i) - 'a') % MOD;
        }
        while(q-->0){
            int l1 = sc.nextInt();
            int r1 = sc.nextInt();
            int l2 = sc.nextInt();
            int r2 = sc.nextInt();
            String res = getHash(l1,r1) == getHash(l2,r2) ? "Yes" : "No";
            System.out.println(res);
        }
    }
    static long getHash(int l ,int r){
        return ((h[r] - h[l - 1] * b[r - l + 1]) % MOD + MOD) % MOD;
    }
}

🍎笔记

((h[r] - h[l - 1] * b[r - l + 1]) % MOD + MOD) % MOD：为了避免取模结果为负数，先对结果取模，再加上 MOD，最后再取模。