给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数n和m，表示字符串长度和询问次数。

第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。

接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从1开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

Go 代码

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

type uul int64 // type unsigned long long uul

const N = 100010
const P = 131

var h []uul // 所有前缀的哈希值
var p []uul // 进制

func main() {
//  file, _ := os.Open("./1.txt")
//  defer file.Close()
    new(os.Stdin)

    h = make([]uul, N)
    p = make([]uul, N)

    reader := readInt()
    n, m := reader[0], reader[1] // 读取字符串的长度 n 和询问次数 m
    str := readLine()[0]         // 读取长度为 n 的字符串
    str = " " + str              // 调整下标从 1 开始
    char := []rune(str)
    p[0] = 1
    for i := 1; i <= n; i++ {
        p[i] = p[i-1] * P
        h[i] = h[i-1]*P + uul(char[i])
    }

    for i := 0; i < m; i++ {
        read := readInt()
        l1, r1, l2, r2 := read[0], read[1], read[2], read[3]
        if get(l1, r1) == get(l2, r2) {
            fmt.Println("Yes")
        } else {
            fmt.Println("No")
        }
    }

}

func get(l, r int) uul {
    return h[r] - h[l-1]*p[r-l+1]
}

var scanner *bufio.Scanner

func new(reader io.Reader) {
    scanner = bufio.NewScanner(reader)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
}

func readInt() []int {
    scanner.Scan()
    line := strings.Split(scanner.Text(), " ")
    res := make([]int, len(line))
    for i, l := range line {
        temp, _ := strconv.Atoi(l)
        res[i] = temp
    }
    return res
}
func readLine() []string {
    scanner.Scan()
    return strings.Split(scanner.Text(), " ")
}