当前位置：首页 > 编程日记 > 正文

Go 语言实现字符串匹配算法 -- BF(Brute Force) 和 RK(Rabin Karp)

编程日记 2024-04-02 09:00:00

今天介绍两种基础的字符串匹配算法，当然核心还是熟悉一下Go的语法，巩固一下基础知识

BF(Brute Force)
RK(Rabin Karp)

源字符串：src, 目标字符串:dest；确认dest是否是src 的一部分。

BF算法很简单暴力，维护两个下标i,j，i控制src的遍历顺序, j控制dest遍历顺序。
记录一下i的起始位置，当j和i所在的字符匹配的时候，j和i都移动，知道j达到末尾则直接返回匹配。
否则i 回到起始位置的下一个位置，j 回到起始位置，两者重新进行匹配搜索。

由于比较简单，直接看一下Go实现的代码即可：

func Brute_force(str1 string, str2 string) bool{if len(str1) < len(str2){return  false}var (begin int = 0 // 维护src的起始位置i intj int)for i = 0; i < len(str1); begin++ {for j = 0;j < len(str2); j++ {if i < len(str1) && str1[i] == str2[j] {i++continue} else {break}}if j == len(str2) {return  true}i = begini++}return false
}

以上最坏的情况下是主串是“aaaaa…aaaaaa”(省略号表示有很多重复的字符a)，模式串是“aaaaab”。我们每次都比对m个字符，要比对n-m+1次，所以，这种算法的最坏情况时间复杂度是O(n*m)。
当然这种模式匹配在实际的软件开发中还是比较常用的，主要有如下两种原因：

实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把m个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。
朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有bug也容易暴露和修复。

接下来看一下第二种算法，Rabin Karp。
这个算法的大体思路是：
过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

在这里插入图片描述

为了提升效率，我们需要尽可能避免遍历字符串中的每一个字符，否则就是仅仅提高了比较效率而已（数值的比较效率）。
hash函数的设计需要精巧一些，假设我们设置的字符集只包含k个字符，我们可以使用一个K进制的数来表示一个字符串，将这个 K进制转化为10进制的值即可作为hash 值。

比如要处理的字符串包括a-z 26个字母，我们可以使用26进制表示一个字符串，同时将26进制转化为一个10进制的值作为这个字符串的hash值。

对于字符串：“hjk”
h: (‘h’- ‘a’) *26^0
j: (‘j’ - ‘a’) * 26^1
j: (‘k’ - ‘a’) * 26^2

hash(“hjk”) = (‘h’- ‘a’) *26^0 + (‘j’ - ‘a’) * 26^1 + (‘k’ - ‘a’) * 26^2

为了减少遍历源字符串中的字符次数，我们可以看看如下规律:
源字符串“hjkl”,我们先取 “hjk”，后取"jkl"

hash(“hjk”) = (‘h’- ‘a’) *26^0 +('j' - 'a') * 26^1 + ('k' - 'a') * 26^2
hash(“jkl”) = ('j' - 'a') * 26^0 + ('k' - 'a')* 26^1 + (‘l’ - ‘a’) * 26^2

依据此规律，我们可以总结出来两个公式：
hash(i-1) = 26^0 * (s[i-1] - ‘a’) + 26^1 * (s[i] - ‘a’) + … + 26^(m-1) * (s[i+m-2] -‘a’)
hash(i) = 26^0 * (s[i] - ‘a’) + … + 26^(m-2) * (s[i + m - 2] - ‘a’) + 26^(m-1) * (s[i+m-2] -‘a’)

i表示源字符串的起始遍历位置字符下标,m表示目标字符串的长度, s表示源字符串 src。

两个公式进行运算：hash(i) - hash(i-1) / 26 = 26^(m-1) * (s[i+m-2] -‘a’) - (26^0 * (s[i-1] - ‘a’)) / 26
最终可以得到: hash(i) = (hash(i-1) - s[i-1] -‘a’ ) / 26 + 26^(m-1) * (s[i+m-2] -‘a’) 这样的计算公式。

这个时候，我们只需要扫描一遍主串即能够完成目标字符串的匹配，主串的长度为n, 也就是我们需要O(n)的扫描复杂度。模式串的hash值和每一个子串的hash值之间的比较是O(1) , 总共需要比较n-m+1个子串的哈希值，所以，这部分的时间复杂度也是O(n)。

所以，RK算法整体的时间复杂度就是O(n)，相比于BF的O(m*n)效率还是高了不少。

Go语言的完整实现如下：

// Calculate a string's hash function
func Hash(str string, m [] int) int {if len(str) == 0 {return 0}var (t intres int = 0)for i := 0; i < len(str); i ++ {t = m[i] * int(str[i] - 'a')res = res + t}return res
}// match the substring with hash function
// we can calculate the string's hash value with below formula
//
// 's' is source string, m is the length of the substring
// h(i-1) = 26^0 * (s[i-1] - 'a') +
// 			26^1 * (s[i] - 'a') + ... +
// 			26^(m-1) * (s[i+m-2] -'a')
//
// h(i) = 26^0 * (s[i] - 'a') + ... +
// 		  26^(m-2) * (s[i + m - 2] - 'a') +
// 		  26^(m-1) * (s[i+m-2] -'a')
//
// so
// h(i) = (h(i-1) - s[i-1] -'a' ) / 26 + 26^(m-1) * (s[i+m-2] -'a')
// we can use the formula to reduce the cpu's calculation
func Rabin_Karp_Hash(str1 string, str2 string) bool {if len(str1) < len(str2) {return false}var m []intvar t int = 1m = append(m,1)for i := 1; i < len(str2) + 1; i ++ {t = t*26m = append(m,t) // m store with 26^0, 26^1, 26^2 ... 26^(len(str2))}str2_hash := Hash(str2, m)fmt.Println(str2_hash)str1_hash := Hash(string([]byte(str1)[:len(str2)]),m)if str2_hash == str1_hash {return  true}for i := 1; i < len(str1) - len(str2) + 1; i ++ {new_hash := (str1_hash - int(str1[i-1]-'a')) / 26 +m[len(str2)-1] * int(str1[i+len(str2) -1] - 'a')if new_hash == str2_hash {return  true} else {str1_hash = new_hash}}return  false
}

https://www.dkcj.cn/info/4068.html

Go 语言实现字符串匹配算法 -- BF(Brute Force) 和 RK(Rabin Karp)

相关文章：

Java项目:前后端分离网上手机商城平台系统设计和实现(java+vue+redis+springboot+mysql+ssm)

利用AutoSPSourceBuilder和Autospinstaller自动安装SharePoint Server 2013图解教程——Part 1...

Git 版本还原命令

NVME CLI -- nvme 命令查看NVME设备内部状态

Java项目:网上水果蔬菜项目系统设计和实现(java+springboot+mysql+ssm)

POJ 1189 记忆化搜索

Android短信管家视频播放器代码备份

Python常用函数--文档字符串DocStrings

Go 分布式学习利器（17）-- Go并发编程之协程机制：Grountine 原理及使用

Java项目:美食菜谱分享平台系统设计和实现(java+springboot+mysql+ssm)

【leetcode】Roman to Integer

Apache Traffic Server管理工具

npm使用记录

Go 分布式学习利器（18）-- Go并发编程之lock+WaitGroup实现线程安全

Java项目:网上家具商城平台设计和实现(java+springboot+mysql+ssm)

Linux socket TIME_WAIT 优化

Android Handler的使用!!!

git之reset图解

Go 分布式学习利器（19）-- Go并发编程之 CSP(communicating sequential processes) 机制

Java项目:学生学科竞赛管理管理系统设计和实现(java+springboot+ssm+maven)

update 改写 merge into

CCControlSwitch 、CCControlSlider、CCControlButton

bzoj2961 共点圆（CDQ分治，凸包）

Rocksdb Iterator实现：从DBIter 到 TwoLevelIter 的漫长链路

Java项目:OA办公自动化系统设计和实现(java+springboot+freemarker+mysql+maven+mybatis+jpa)

UIScrollView上面放一个UIScrollView或者UITableView拖动时候 View出现一闪一闪解决办法...

理解koa-router 路由一般使用

Go 分布式学习利器（20）-- Go并发编程之多路选择和超时控制,channel的关闭和广播

Java项目:网盘系统设计和实现(java+ssm+jpa)

快速学习的方法论