golang实现字符串哈希md

golang实现字符串哈希

算法题目

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。 字符串中只包含大小写英文字母和数字。 输入格式 第一行包含整数n和m，表示字符串长度和询问次数。 第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。 接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。 注意，字符串的位置从1开始编号。 输出格式 对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。 每个结果占一行。 数据范围 1≤n,m≤10^5

输入样例：

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

输出结果：

Yes No Yes

golang实现

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) const N = 100010 const P =131 // P进制,也可取值13331，这样哈希后冲突最小 var (n,m int h,p [N]int64) func readint(r *bufio.Reader)[]int { s,_ :=r.ReadString('\n') ss :=strings.Fields(s) res :=make([]int,len(ss)) for i,v :=range ss{ res[i],_ = strconv.Atoi(v) } return res } func get(l,r int)int64 { return h[r]-h[l-1]*p[r-l+1] } func main() { r :=bufio.NewReader(os.Stdin) in :=readint(r) n,m = in[0],in[1] // 每个字符的哈希处理 s,_:=r.ReadString('\n') s = " "+s //不能以0开始 A^0=0,AA^0=0 char :=[]rune(s)//rune处理后的都是int32 p[0]=1 for i:=1;i<=n;i++{ p[i] = p[i-1]*P h[i] = h[i-1]*P+int64(char[i]) } // 读取每次的操作 for m>0{ m-- in = readint(r) l1,r1,l2,r2 :=in[0],in[1],in[2],in[3] if get(l1,r1)==get(l2,r2){ fmt.Println("Yes") }else { fmt.Println("No") } } }

不使用rune处理的方式

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) const ( N = 100010 P = 131 ) var st[N]int64 var p,h [N]int64 func readLine(r *bufio.Reader) []int { s, _ := r.ReadString('\n') sSlice := strings.Fields(s) res := make([]int, len(sSlice)) for i, k := range sSlice { res[i], _ = strconv.Atoi(k) } return res } func get(l,r int) int64 { return h[r]-h[l-1]*p[r-l+1] } func main() { r := bufio.NewReader(os.Stdin) var n, m int in := readLine(r) n, m = in[0], in[1] s,_ :=r.ReadString('\n') //ss :=strings.Fields(s) for i,v:=range s{ //for i:=1;i<=len(s);i++{ // st[i] = s[i-1] st[i+1] = int64(v) } //fmt.Println(st[:len(s)]) p[0]=1 //预处理p和h for i := 1; i <= n; i++ { //u ,_:=strconv.Atoi(st[i]) h[i] = h[i - 1] * P + st[i] p[i] = p[i - 1] * P } fmt.Println(h[:n+1]) for ;m>0;m--{ in=readLine(r) l1, r1, l2, r2 := in[0], in[1], in[2], in[3] if get(l1, r1) == get(l2, r2) { fmt.Println("Yes") } else { fmt.Println("No") } } }