C
#include <stdio.h>
#define MAXSIZE 100010
#define POWER 13331 // or 131
int i, n, m, l1, r1, l2, r2;
char s[MAXSIZE];
unsigned long long h[MAXSIZE], power[MAXSIZE]; // mod 2<<64
void init() {
power[0] = 1;
for (i = 1; i <= n; ++i) {
power[i] = power[i-1] * POWER;
h[i] = h[i-1] * POWER + s[i];
}
}
unsigned long long substrHash(int left, int right) {
return h[right] - h[left-1] * power[right-left+1];
}
int main() {
scanf("%d%d%s", &n, &m, s+1);
init();
while (m--) {
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (substrHash(l1, r1) == substrHash(l2, r2)) {
puts("Yes");
} else {
puts("No");
}
}
return 0;
}
Go
package main
import (
"bufio"
"fmt"
"os"
)
const POWER uint64 = 13331
var (
n, m, l1, r1, l2, r2 int
s string
h, power []uint64
)
func prepare() {
h, power = make([]uint64, n+1), make([]uint64, n+1)
power[0] = 1
for i := 1; i <= n; i++ {
power[i] = power[i-1] * POWER
h[i] = h[i-1]*POWER + uint64(s[i-1])
}
}
func substrHash(left, right int) uint64 {
return h[right] - h[left-1]*power[right-left+1]
}
func main() {
in := bufio.NewReader(os.Stdin)
fmt.Fscan(in, &n, &m, &s)
prepare()
for i := 0; i < m; i++ {
fmt.Fscan(in, &l1, &r1, &l2, &r2)
if substrHash(l1, r1) == substrHash(l2, r2) {
fmt.Println("Yes")
} else {
fmt.Println("No")
}
}
}