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();// hashb[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，最后再取模。