2023-11-11：用 go 语言，字符串哈希 + 二分的例题。给定长为 n 的源串 s，以及长度为 m 的模式串 p，要求查找源串中有多少子串与模式串匹配， s‘ 与 s 匹配，当且仅当 s‘ 与 s

作者：福大大架构师每日一题

2023-11-11
北京
本文字数：2572 字
阅读完需：约 8 分钟

2023-11-11：用 go 语言，字符串哈希+二分的例题。

给定长为 n 的源串 s，以及长度为 m 的模式串 p，

要求查找源串中有多少子串与模式串匹配，

s' 与 s 匹配，当且仅当 s' 与 s 长度相同，且最多有 k 个位置字符不同。

其中 1 <= n, m <= 10^6，0 <= k <= 5。

来自左程云。

答案 2023-11-11：

go 代码用灵捷 3.5 编写。

大体过程如下：

算法 1：

遍历源串 s 中所有长度为 m 的子串，判断子串与模式串的不同字符数量是否小于等于 k，若是，将统计的子串数量加 1。具体地：

1.首先计算源串 s 的长度 n 和模式串 p 的长度 m。

2.若 n < m，则返回 0。

3.将源串 s 和模式串 p 转换为 rune 类型的切片，方便进行字符比较。

4.遍历源串 s 中所有长度为 m 的子串，判断子串与模式串的不同字符数量是否小于等于 k，若是，将统计的子串数量加 1。

5.返回统计的子串数量。

算法 2：

计算源串 s 的哈希值和模式串 p 的哈希值，然后遍历源串 s 中所有长度为 m 的子串，判断子串与模式串的哈希值是否相等，若是则比较子串与模式串的每个字符是否相同，最多允许 k 个字符不同。具体地：

1.首先计算源串 s 的长度 n 和模式串 p 的长度 m。

2.若 n < m，则返回 0。

3.将源串 s 和模式串 p 转换为 rune 类型的切片，方便进行哈希操作。

4.计算源串 s 的哈希值和模式串 p 的哈希值，分别保存在 hashs 和 hashp 数组中。

5.遍历源串 s 中所有长度为 m 的子串，判断子串与模式串的哈希值是否相等，若是则比较子串与模式串的每个字符是否相同，最多允许 k 个字符不同。

6.比较子串与模式串的每个字符是否相同，最多允许 k 个字符不同的具体实现：遍历子串中每个字符，二分查找在模式串中与该字符相同的位置，若找到了，则比较子串和模式串中该位置的字符是否相同，否则允许 k 的值加 1。如果 k 的值大于了允许的最大值，那么返回 false。

7.返回 true。

时间复杂度和空间复杂度分析：

算法 1：

时间复杂度：代码中主要的时间复杂度来源于遍历源串 s 中所有长度为 m 的子串，遍历次数为 O(n-m+1)，每次遍历需要比较 m 个字符，因此总的时间复杂度为 O((n-m+1)*m)。由于 n 和 m 的值均不超过 10^6，因此算法 1 的总的时间复杂度为 O(10^12)，在实际情况中运算速度较慢。

空间复杂度：算法 1 只需要占用 O(n+m) 的额外空间，用于存储源串 s 和模式串 p。

算法 2：

时间复杂度：代码中主要的时间复杂度来源于计算源串 s 和模式串 p 的哈希值，以及遍历源串 s 中所有长度为 m 的子串，遍历次数为 O(n-m+1)，每次需要计算哈希值和比较 m 个字符，因此总的时间复杂度为 O((n-m+1)*(m+logn))。由于 n 和 m 的值均不超过 10^6，因此算法 2 的总的时间复杂度为 O(10^12)，与算法 1 的时间复杂度相同，但实际速度更快。

空间复杂度：算法 2 需要占用 O(n+m) 的额外空间，用于存储源串 s 和模式串 p 的哈希值，以及 O(n) 的额外空间，用于存储哈希值计算过程中的幂 base^i(i<=n)。

总结：

算法 1 和算法 2 的时间复杂度都为 O(10^12)，但实际运算速度可能存在很大的差异，具体取决于实现过程中的细节。在实际应用中，算法 2 比算法 1 更为常用，因为哈希算法能够在较快的时间内完成字符串的比较。

go 完整代码如下：

package main
import (  "fmt"  "math/rand")
func howMany1(str1 string, str2 string, k int) int {  n := len(str1)  m := len(str2)  if n < m {    return 0  }  s := []rune(str1)  p := []rune(str2)  ans := 0  for i := 0; i <= n-m; i++ {    if diffLessK1(s, i, p, k, m) {      ans++    }  }  return ans}
func diffLessK1(s []rune, i int, p []rune, k int, m int) bool {  diff := 0  for j := 0; j < m; j++ {    if s[i+j] != p[j] {      diff++    }  }  return diff <= k}
const MAXN = 100001const base = 1000000007
var pow []int64 = make([]int64, MAXN)var hashs []int64 = make([]int64, MAXN)var hashp []int64 = make([]int64, MAXN)
func buildHash(s []rune, n int, p []rune, m int) {  hashs[0] = int64(s[0] - 'a' + 1)  for j := 1; j < n; j++ {    hashs[j] = hashs[j-1]*base + int64(s[j]-'a'+1)  }  hashp[0] = int64(p[0] - 'a' + 1)  for j := 1; j < m; j++ {    hashp[j] = hashp[j-1]*base + int64(p[j]-'a'+1)  }}
func howMany2(str1 string, str2 string, k int) int {  n := len(str1)  m := len(str2)  if n < m {    return 0  }  s := []rune(str1)  p := []rune(str2)  buildHash(s, n, p, m)  ans := 0  for i := 0; i <= n-m; i++ {    if diffLessK2(i, i+m-1, 0, m-1, k) {      ans++    }  }  return ans}
func diffLessK2(l1 int, r1 int, l2 int, r2 int, k int) bool {  diff := 0  for l1 <= r1 && diff <= k {    l, r := 1, r1-l1+1    len := 0    for l <= r {      m := (l + r) / 2      if ok(l1, l2, m) {        len = m        l = m + 1      } else {        r = m - 1      }    }    if l1+len <= r1 {      diff++    }    l1 += len + 1    l2 += len + 1  }  return diff <= k}
func ok(l1 int, l2 int, len int) bool {  return hash(hashs, l1, l1+len-1) == hash(hashp, l2, l2+len-1)}
func hash(hash []int64, l int, r int) int64 {  ans := hash[r]  if l == 0 {    return ans  }  ans -= hash[l-1] * pow[r-l+1]  return ans}
func init() {  pow[0] = 1  for j := 1; j < MAXN; j++ {    pow[j] = pow[j-1] * base  }}
// 生成随机子串func randomString(len int, rangeNum int) string {  b := make([]byte, len)  for i := 0; i < len; i++ {    b[i] = byte(rand.Intn(rangeNum) + 'a')  }  return string(b)}
func main() {  N := 100  M := 50  K := 10  // a b c  // R =4 abcd  R := 3  testTimes := 10000  fmt.Println("测试开始")  for i := 0; i < testTimes; i++ {    n := rand.Intn(N) + 1    m := rand.Intn(M) + 1    k := rand.Intn(K)    str1 := randomString(n, R)    str2 := randomString(m, R)    ans1 := howMany1(str1, str2, k)    ans2 := howMany2(str1, str2, k)    if ans1 != ans2 {      fmt.Println("出错了！")    }  }  fmt.Println("测试结束")}