AcWing 841. 字符串哈希--java
原题链接
简单
作者:
Fonaldinho
,
2020-10-11 20:15:58
,
所有人可见
,
阅读 593
import java.util.*;
public class Main{
static int N = 100010, P = 131;
static long[] h = new long[N];
static long[] p = new long[N];
static char[] str;
static long get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
String s = " " + sc.next();
str = s.toCharArray();
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
}
while(m -- > 0){
int l1 = sc.nextInt(), r1 = sc.nextInt(), l2 = sc.nextInt(), r2 = sc.nextInt();
if(get(l1, r1) == get(l2, r2)) System.out.println("Yes");
else System.out.println("No");
}
}
}
这个代码确实牛逼,非常朴素的方式,简单易懂的键盘输入,通俗易懂