AcWing 841. 字符串哈希_Java含注释
原题链接
简单
作者:
FayunYm
,
2020-12-30 12:19:51
,
所有人可见
,
阅读 347
import java.io.*;
public class StringHash {
static final int N = 100_010;
static long[] h = new long[N];
static long[] p = new long[N]; //用来存放权重,减少后面的重复运算
static final int P =131; //经验值,取131,或13331不容易冲突
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
String[] param = reader.readLine().split(" ");
int n = Integer.parseInt(param[0]);
int m = Integer.parseInt(param[1]);
String str = "x"+reader.readLine().substring(0,n); //substring和C++有点不一样;第一位x无意义只是占个位
p[0] = 1;
// h[0] = 0;
for(int i = 1; i <= n; i++) {
p[i] = p[i-1] * P; //计算每一位权重
h[i] = h[i-1] * P + str.charAt(i); //h用来存放每一段前缀对应的hash值(取模后的,模是2^64,刚好是按long取模)
}
while(m-- != 0) {
String[] op = reader.readLine().split(" ");
int l1 = Integer.parseInt(op[0]);
int r1 = Integer.parseInt(op[1]);
int l2 = Integer.parseInt(op[2]);
int r2 = Integer.parseInt(op[3]);
if(get(l1,r1) == get(l2,r2)) {
log.write("Yes\n");
} else log.write("No\n");
}
log.flush();
log.close();
reader.close();
}
private static long get(int l, int r) {
return h[r] - h[l-1] * p[r-l+1];
}
}