AcWing 138. 兔子与兔子 java
原题链接
简单
字符串hash
import java.io.*;
class Main {
static int N = 1000010;
static long[] h = new long[N]; // 存放从1到i字符串的hash值
static long[] p = new long[N]; // 存放第i个字符的hash值
static int base = 131;
static long get(int l, int r) { // 计算子串从 l 到 r 的hash值
return h[r] - h[l - 1]*p[r - l + 1];
}
public static void main(String[] args) throws IOException{
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
char[] c = cin.readLine().toCharArray();
int n = c.length;
char[] s = new char[N];
System.arraycopy(c, 0, s, 1, n);
p[0] = 1; // n^0 == 1
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * base + s[i] - 'a' + 1;
p[i] = p[i - 1] * base;
}
int m = Integer.parseInt(cin.readLine());
int l1, r1, l2, r2;
while (m-- > 0) {
String[] str = cin.readLine().split(" ");
l1 = Integer.parseInt(str[0]);
r1 = Integer.parseInt(str[1]);
l2 = Integer.parseInt(str[2]);
r2 = Integer.parseInt(str[3]);
if(get(l1, r1) == get(l2, r2)) System.out.println("Yes");
else System.out.println("No");
}
}
}
long溢出为负数,不会有问题么
不会,可以进行粗略检验最大值为
3915584334365810824
不会超过 long 的范围,一般题目也不会超过 long 的这个粗略计算是怎么算出来的?最大值不应该是$26^{100000}$ 吗
可以把long当无符号long使用,溢出就变成取mod了。
溢出的话不是变负数吗
看long的二进制,toString()是按补码打印,肯定显示为负数。你可以试试Long.toUnsignedString()