AcWing 841. 字符串哈希-java
原题链接
中等
作者:
韦德
,
2021-06-13 20:12:37
,
所有人可见
,
阅读 240
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static class StringHash{
String s;
int p = 131;
int[] m,h;
StringHash(String str){
s = str;
m = new int[s.length() + 1];
m[0] = 1;
h = new int[s.length() + 1];
for (int i = 1;i<=s.length();i++){
m[i] = m[i-1] * p;
h[i] = h[i-1] * p + s.charAt(i-1);
}
}
// a b c d e
int getStringHash(int l,int r){
return h[r] - h[l-1] * m[r - l + 1];
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] first = reader.readLine().split(" ");
int m = Integer.parseInt(first[1]);
String s = reader.readLine();
StringHash sh = new StringHash(s);
while (m > 0){
m--;
String[] cur = reader.readLine().split(" ");
int l1 = Integer.parseInt(cur[0]);
int r1 = Integer.parseInt(cur[1]);
int l2 = Integer.parseInt(cur[2]);
int r2 = Integer.parseInt(cur[3]);
System.out.println(sh.getStringHash(l1,r1) == sh.getStringHash(l2,r2) ? "Yes":"No");
}
}
}