AcWing 841. 字符串哈希
原题链接
简单
作者:
Astarion
,
2021-02-06 11:58:01
,
所有人可见
,
阅读 291
import java.io.*;
class Main {
static int P = 131;
static long[] h = new long[100010];
static long[] p = new long[100010];
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int m = Integer.parseInt(strs[1]);
char[] s = in.readLine().toCharArray();
p[0] = 1;
h[0] = s[0];
for (int i = 1; i<=n; i++) {
h[i] = h[i-1]*P + s[i-1];
p[i] = p[i-1]*P;
}
for (int i = 0; i<m; i++) {
strs = in.readLine().split(" ");
int x1 = Integer.parseInt(strs[0]);
int y1 = Integer.parseInt(strs[1]);
int x2 = Integer.parseInt(strs[2]);
int y2 = Integer.parseInt(strs[3]);
long hash1 = h[y1] - h[x1-1]*p[y1-x1+1];
long hash2 = h[y2] - h[x2-1]*p[y2-x2+1];
if (hash1 == hash2) System.out.println("Yes");
else System.out.println("No");
}
}
}