主体思想
注意细节
字符串记得前面加“ ”
基础代码 优化写法
少写10多行代码,速度也不见的比初版的慢
package main
import (
"fmt"
"os"
"bufio"
)
const (
N = 100010
P = 131
)
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewReader(os.Stdin)
h, p [N]int64
n, m int
s string
l1, r1, l2, r2 int
)
func get(l, r int) int64 {
return h[r] - h[l - 1] * p[r - l + 1]
}
func main() {
fmt.Fscan(in, &n, &m, &s)
s = " " + s
p[0] = 1
for i := 1; i <= n; i++ {
h[i] = h[i - 1] * P + int64(s[i])
p[i] = p[i - 1] * P
}
for ; m > 0; m-- {
fmt.Fscan(in, &l1, &r1, &l2, &r2)
if get(l1, r1) != get(l2, r2) {
fmt.Fprint(out, "No\n")
} else {
if s[l1 + 1: r1 + 1] == s[l2 + 1: r2 + 1] {fmt.Fprint(out, "Yes\n")}
}
}
out.Flush()
}
基础代码
package main
import (
"fmt"
"os"
"bufio"
"strings"
"strconv"
)
const (
N = 100010
P = 131
)
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewScanner(os.Stdin)
bs = make([]byte, 20000 * 1024)
readLine = func() (res []string) {
in.Scan()
res = strings.Split(in.Text(), " ")
return
}
h, p [N]int64
)
func get(l, r int) int64 {
return h[r] - h[l - 1] * p[r - l + 1]
}
func main() {
in.Buffer(bs, len(bs))
cur := readLine()
n, _ := strconv.Atoi(cur[0])
m, _ := strconv.Atoi(cur[1])
cur = readLine()
str := cur[0]
str = " " + str
p[0] = 1
for i := 1; i <= n; i++ {
h[i] = h[i - 1] * P + int64(str[i])
p[i] = p[i - 1] * P
}
for ; m > 0; m-- {
cur = readLine()
l1, _ := strconv.Atoi(cur[0])
r1, _ := strconv.Atoi(cur[1])
l2, _ := strconv.Atoi(cur[2])
r2, _ := strconv.Atoi(cur[3])
if get(l1, r1) != get(l2, r2) {
fmt.Fprint(out, "No\n")
} else {
if str[l1 + 1: r1 + 1] == str[l2 + 1: r2 + 1] { fmt.Fprint(out, "Yes\n") } // 严格验证:哈希值 + 字符一样
}
out.Flush()
}
}