C++ 代码
#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
typedef unsigned long long ULL;
const int N = 1000010,P=131;
char str[N];
ULL h[N],p[N];
ULL get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
scanf("%s", str+1);
int n=strlen(str+1);
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*P+str[i]-'a'+1;
p[i]=p[i-1]*P;
}
scanf("%d", &m);
while(m--){
int l1,r1,l2,r2;
scanf("%d%d%d%d", &l1, &r1,&l2,&r2);
if(get(l1,r1)==get(l2,r2)){
puts("Yes");
}else{
puts("No");
}
}
return 0;
}
java 代码
import java.util.Scanner;
class Main {
private static final int base = 131; // 哈希基数,通常选取一个较大的质数
private static final long INF = Long.MIN_VALUE; // 用于处理溢出的常量
private static final String Y = "Yes";
private static final String N = "No";
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next(); // 读取输入字符串
int m = in.nextInt(); // 读取查询次数
int[][] q = new int[m][4];
// 读取每次查询的左右边界
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 4; ++j) {
q[i][j] = in.nextInt();
}
}
in.close();
solve(s, q);
}
// 计算子串哈希值的方法
private static long get(long[] hash, long[] pow, int l, int r) {
long right = hash[r];
long left = hash[l - 1];
long ans = right - left * pow[r - l + 1]; // 计算哈希值
if (ans < 0) ans -= INF; // 处理溢出情况
return ans;
}
// 预处理幂次的方法
private static long[] pow(int n) {
long[] pow = new long[n];
pow[0] = 1;
// 计算每个位置的幂次值
for (int i = 1; i < n; ++i) {
pow[i] = pow[i - 1] * base;
if (pow[i] < 0) pow[i] -= INF; // 处理溢出情况
}
return pow;
}
// 预处理字符串哈希值的方法
private static long[] hash(String s) {
long[] hash = new long[s.length() + 1];
hash[0] = 0;
// 计算字符对应的哈希值
for (int i = 0; i < s.length(); ++i) {
hash[i + 1] = base * hash[i] + s.charAt(i) - 'a' + 1;
if (hash[i + 1] < 0) {
hash[i + 1] -= INF; // 处理溢出情况
}
}
return hash;
}
// 解决问题的主方法
private static void solve(String s, int[][] query) {
StringBuilder sb = new StringBuilder();
long[] pow = pow(s.length() + 1);
long[] hash = hash(s);
// 遍历每个查询
for (int[] q : query) {
// 比较两个子串的哈希值是否相等
if (get(hash, pow, q[0], q[1]) == get(hash, pow, q[2], q[3])) {
sb.append(Y);
} else {
sb.append(N);
}
sb.append("\n");
}
System.out.print(sb);
}
}