知识点补充

字符串前缀hash
    1. 解决字符串相关的问题，eg:两个子串是否相等
    2. 思想
        - 求出字符串每个前缀的hash值 eg "ABC" 分别求出A的hash值， AB的hash值，ABC的hash值
            - 用p进制的数来表示hash值 经验值 p=131或者13331
                eg: h[1] = h[1] * P + A的ascii
            - 因为当字符串越长，前缀的hash值越大，不好存储 所以mod 2的64次方即可 即 Q = 2^64
            - pq这样取会减少冲突，注意这里想的是没有冲突，并且从1开始映射
        - 然后求出LR之间字符串的hash值，比较是否相等 相等则两个字串相同
            - 问题来了，怎么求LR之间的hash值那？
            - h[r] - h[l - 1] * p[r - l + 1];

题目描述

输入n和m，n代表字符串长度，m代表m次操作，每次给两个字串的位置，判断两个字串是否相等

输入样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输入样例

Yes
No
Yes

算法1

(字符串前缀hash) $O(1)$

思路见知识点补充

时间复杂度：$O(1)$

参考文献：y总

Java 代码

import java.io.*;

public class Main {
    static int N = 100010;
    static int P = 131;// 经验值
    static int[] h = new int[N];// 存放前缀hash值
    static int[] p = new int[N];// 存放131^0  131^1  131^2

    // 获取LR之间的hash值
    static long getStringHash(int l, int r){
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String s2 = br.readLine();
        // 预编译
        p[0] = 1;// 初始是1
        for (int i = 1; i <= n; i++){
            h[i] = h[i - 1] * P + s2.charAt(i - 1);// 存放前缀hash值
            p[i] = p[i - 1] * P;// 存放131的i次方
        }

        while (m-- > 0){
            s = br.readLine().split(" ");
            int l1 = Integer.parseInt(s[0]);int r1 = Integer.parseInt(s[1]);
            int l2 = Integer.parseInt(s[2]);int r2 = Integer.parseInt(s[3]);
            long zc1 = getStringHash(l1, r1);
            long zc2 = getStringHash(l2, r2);
            System.out.println(zc1 == zc2?"Yes":"No");
        }
        br.close();
    }
}