关于后端:字符串匹配的Rabin–Karp算法

leetcode-28 实现 strStr()

更相熟的字符串匹配算法可能是 KMP 算法, 但在 Golang 中, 应用的是 Rabin–Karp 算法

个别中文译作 拉宾 - 卡普算法, 由迈克尔·拉宾与理查德·卡普于 1987 年提出

要在一段文本中找出单个模式串的一个匹配，此算法具备线性工夫的均匀复杂度，其运行工夫与待匹配文本和模式串的长度成线性关系。尽管均匀状况下，此算法体现优异，但最坏状况下，其复杂度为文本长与模式串长的乘积

尽可能多的利用上一步的后果，这是优化工夫复杂度的一大外围

对于数字类型的字符串，可有如下匹配办法：

将该办法扩大到非数字类型的字符串：

<font size=1>
以上这张图片的 LaTex：

$$\begin{gather}
  
对于长度为 n 的字符串 x_{0} x_{1} x_{2} ... x_{n-1},\\ 其对应的“值”val 为 \\

val = x_{0} \times r^{n-1} + x_{1}\times r^{n-2} + ... +  x_{n-1}\times r^{0}
 
 \\ 其中 r 为进制数 \end{gather}$

</font>

<font size=1 color=”grey”>

ASCII：英语字符与二进制位之间的关系
(其余语言？？)

Unicode：将世界上所有的符号都纳入其中，
每个符号都对应一个举世无双的编码，最多能够包容 1114112 个字符(2021 年 9 月颁布的 14.0.0，曾经收录超过 14 万个字符)
(有个问题是节约空间。。) 也译作对立码 / 万国码 / 国内码

UTF-8: 应用最广的一种 Unicode 的实现形式
(最大特点是 变长的编码方式)

字符编码笔记：ASCII，Unicode 和 UTF-8

中日韩汉字 Unicode 编码表

</font>

源码正文：

将源码中的 16777619 进制改为 10 进制，从字符串 31415926 中搜寻 4159：

4159

package main

import (
    "fmt"
    "strconv"
)

func main() {

    var primeRK uint32 = 10
    sep := "4159"
    hash := uint32(0)
    for i := 0; i < len(sep); i++ {//fmt.Println(sep[i])
        //fmt.Println(string(sep[i]))
        next, _ := strconv.Atoi(string(sep[i]))
        //hash = hash*primeRK + uint32(sep[i])
        hash = hash*primeRK + uint32(next)
        fmt.Println(hash)
    }
    
}

输入为：

4
41
415
4159

残缺的以 10 为 primeRK，从 31415926 中搜寻 4159 的代码：

package main

import (
    "fmt"
    "strconv"
)

const PrimeRKNew = 10

func main() {
    str := `31415926`
    substr := "4159"

    fmt.Println("最终后果为:",  IndexRabinKarpNew(str, substr))
}

func HashStrNew(sep string) (uint32, uint32) {hash := uint32(0)

    for i := 0; i < len(sep); i++ {//fmt.Println(sep[i])
        //fmt.Println(string(sep[i]))
        next, _ := strconv.Atoi(string(sep[i]))
        //hash = hash*primeRK + uint32(sep[i])
        hash = hash*PrimeRKNew + uint32(next)
        fmt.Println(hash)
    }

    var pow, sq uint32 = 1, PrimeRKNew
    for i := len(sep); i > 0; i >>= 1 {fmt.Println("i is:", i, "---", "i&1 is:", i&1)
        if i&1 != 0 {pow *= sq}
        sq *= sq
        fmt.Println("pow is:", pow)
    }
    return hash, pow
}

func IndexRabinKarpNew(s, substr string) int {
    // Rabin-Karp search
    hashss, pow := HashStrNew(substr)
    fmt.Println("hashss, pow:", hashss, pow)

    fmt.Println("~~~ 分割线~~~")

    n := len(substr)
    var h uint32
    for i := 0; i < n; i++ {next1, _ := strconv.Atoi(string(s[i]))
        //h = h*PrimeRKNew + uint32(s[i])
        fmt.Println("next1 is:", next1)
        h = h*PrimeRKNew + uint32(next1)
    }

    fmt.Println("h 即 T 串初始值为:", h)

    if h == hashss && s[:n] == substr {return 0}
    for i := n; i < len(s); {
        h *= PrimeRKNew
        fmt.Println("h*=:", h)

        last, _ := strconv.Atoi(string(s[i])) // 以后 T 串的最初一个元素
        fmt.Println("last is:", last)
        //h += uint32(s[i])
        h += uint32(last)
        fmt.Println("h+=:", h)

        //h -= pow * uint32(s[i-n])
        first, _ := strconv.Atoi(string(s[i-n])) // 以后 T 串的第一个元素
        fmt.Println("first is:", first)
        h -= pow * uint32(first)
        fmt.Println("h-=:", h)

        i++
        fmt.Println("--- 下次循环的 i 为 ---", i)
        if h == hashss && s[i-n:i] == substr {//s[i-n:i]为以后的 T 串
            return i - n
        }
    }
    return -1
}

输入为：

4
41
415
4159
i is: 4 --- i&1 is: 0
pow is: 1
i is: 2 --- i&1 is: 0
pow is: 1
i is: 1 --- i&1 is: 1
pow is: 10000
hashss, pow: 4159 10000
~~~ 分割线~~~
next1 is: 3
next1 is: 1
next1 is: 4
next1 is: 1
h 即 T 串初始值为: 3141
h*=: 31410
last is: 5
h+=: 31415
first is: 3
h-=: 1415
--- 下次循环的 i 为 --- 5
h*=: 14150
last is: 9
h+=: 14159
first is: 1
h-=: 4159
--- 下次循环的 i 为 --- 6
最终后果为: 2

strings.Contains()源码浏览暨 internal/bytealg 初探

书籍举荐

柔性字符串匹配

牛刀小试:

力扣 28. 实现 strStr()

力扣 187. 反复的 DNA 序列

力扣 686. 反复叠加字符串匹配

另：

除去 KMP 和 RK 算法，字符串匹配还有 Boyer-Moore 算法 (简称BM 算法) 系列算法，其核心思想是：

在字符串匹配过程中，模式串发现不匹配时，跳过尽可能多的字符以进行下一步的匹配，从而进步匹配效率

BM 算法的简化版 Horspool 算法

以及性能更好的 Sunday 算法

Python 用的也不是 KMP，而是 boyer-moore 和 horspool, 源码点此

KMP 算法的理论利用有哪些？

图解字符串匹配之 Horspool 算法和 Boyer-Moore 算法

本文由 mdnice 多平台公布