字符串哈希-字符串前缀和hash-golang

blablabla

样例

package main
import(
    "fmt"
    "bufio"
    "os"
    "strings"

    "strconv"
)

var n, m int
var h, p []int
var P = 131

func main(){
    fmt.Scanf("%d%d", &n, &m)
    h, p = make([]int, n+1), make([]int, n+1)
    var str string
    fmt.Scanf("%s", &str)
    str = " " + str
    runeSli := []rune(str)
    p[0] = 1
    for i := 1; i <= n; i++{
        p[i] = p[i-1]*P
        h[i] = h[i-1]*P + int(runeSli[i])
    }

    scan := bufio.NewScanner(os.Stdin)
    for i := m; i > 0; i--{
        scan.Scan()
        data := strings.Split(scan.Text(), " ")

        l1, _ := strconv.Atoi(data[0])
        r1, _ := strconv.Atoi(data[1])
        l2, _ := strconv.Atoi(data[2])
        r2, _ := strconv.Atoi(data[3])
        if get(l1, r1) == get(l2, r2){
            fmt.Println("Yes")
        }else{
            fmt.Println("No")
        }
    }
}

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