题目描述

blablabla

样例

 A B C D
 1 2 3 4
=1*P^3 + 2*P^2 + 3*P^1 + 4*P^0 
-> (1*P^3 + 2*P^2 + 3*P^1 + 4*P^0 ) mod Q

公式
若已知一个|S|=n 的字符串的hash值，hash[i],1≤ i ≤ n，其子串sl..sr,1≤l≤r≤n对应的hash值为：

hash[l,r] = hash[r] − hash[l−1]∗p^(r−l+1)

算法1

Java 代码

import java.io.*; 
import java.util.*;

public class Main{

    static int N = 100010;
    static int P = 131;
    static char[] c = new char[N];
    static long[] p = new long[N];
    static long[] h = new long[N];

    static long get(int l,int r){
        return h[r] - h[l-1]*p[r-l+1];
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split("\\s+");
        int n = Integer.valueOf(s[0]);
        int m = Integer.valueOf(s[1]);
        String str = br.readLine();
        p[0] = 1;
        for(int i=1;i<=n;i++){
            p[i] = p[i-1]*P;
            h[i] = h[i-1]*P + str.charAt(i-1);
        }
        while(m-- > 0){
            String[] strs = br.readLine().split("\\s+");
            int l1 = Integer.valueOf(strs[0]);int r1 = Integer.valueOf(strs[1]);
            int l2 = Integer.valueOf(strs[2]);int r2 = Integer.valueOf(strs[3]);
            if(get(l1,r1)==get(l2,r2))  System.out.println("Yes");
            else    System.out.println("No"); 
        }
    }

}