字符串匹配算法基础版

冷不防 2022-10-01 06:48 98阅读 0赞

最近小谭又被问了一个问题，编程语言中的字符串匹配函数是怎么实现的，是啥原理。

看来大猫又要展示他靠才华吃面的大招了。

小谭一边心里犯嘀咕，这还能有啥原理，直接用不就行了，管那么多干啥，一边对大猫说，今天又想要吃啥面了。

大猫就是这样，经常问你一个问题，你要不会，然后让你请他吃碗面，他给你讲清楚。

大猫腼腆一笑表示今天吃一碗拉面就行，估计是今天这个大招的技术含量不够高吧，一碗拉面就给应付了。

果然，大猫仅用 5 个字就形容了他的大招，**暴力匹配法**，小谭一听暴力法，眉头一皱，貌似也想到了答案，大猫赶紧继续补充。

暴力匹配就是用最原始、最笨的方法去匹配，把两个字符串分别称作目标字符串和模式字符串，然后要判断在目标字符串中能否匹配到模式字符串。

小谭灵光一闪，迫不及待的说出了自己的思路，这个简单啊，**不就是从目标串第一个字符和模式串的第一个字符开始比较，如果两个字符相同，则继续比较两者后面的字符，否则，将模式串移动到目标串的第二个字符重新开始比较**。

大猫有点着急了，眼看自己的大招已然被识破，赶紧顺势总结了一番。

是哒，这就是最常规的思路，也是最简单的算法，这个暴力匹配算法被称作 **BF (bure force)** 算法。

小谭依然追问到，这个算法没啥技术含量，就是用的笨方法，还有没有更好一点的，不然都不值这碗拉面。

有，还真有比这更好一点的，不过要加个卤蛋才可以。看样子大猫早就准备好的了，满满的套路。

我们可以使用哈希算法来优化 BF 算法，大猫看起来很得意的样子。

为啥要用哈希呢，怎么用，小谭有点不太明白。

你看在 BF 算法中，每次都是拿目标字符串和模式串一个字符一个字符的比较，这样很耗时间。

如果目标串的长度为 a，模式串的长度为 b，那么目标串其实就可以拆成 (a-b+1) 个子串…

等等，为啥是 (a-b+1) 呢，小谭有点疑惑。

我给你画张图你就明白了，大猫边说边开始在手机上画起了图。

目标串长度为6，模式串长度为3，所以目标串一共有4个子串

接下来其实就是把这 (a-b+1) 个子串和模式串挨个比较即可。

那这里也没有特别的啊，也没用到哈希函数啊，小谭紧接着问大猫。

别急啊，关键就在下面的哈希函数了，**我们把目标字符串中的每个子串和模式串都使用一个哈希函数来获得哈希值，然后我们就可以直接比较其对应的哈希值就可以了，由于哈希值是一个数字，数字之间的比较是很快的**。因此，判断模式串是否在目标串中，只需要比较两者是否有相等的哈希值就好了。

这个思路有点巧妙啊，小谭有点茅塞顿开的感觉了。

这其实只是一个思路，核心在于这个哈希函数的设计，比如如果存在哈希冲突怎么处理，怎么只遍历一次目标串即可算出所有子串的哈希值，这些都是这个哈希函数要解决的问题，另外这种算法叫做 **RK 算法**，是两位外国人名字的首字母组合而成。

这碗拉面总算是值了，不过最后这个哈希函数的具体设计下回还得继续讲清楚啊。。。

没问题啊，不过我也还得回去再查查资料重新学习下，争取下回给你讲明白，今天给你讲的就是个主要的思路。。。

转载于:https://juejin.im/post/5ce4aab36fb9a07ee63f3b9d

发表评论取消回复

表情：

评论列表（有 0 条评论，98人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串匹配算法

主要算法：BF RK BM KMP Sunday算法 BF ：Brute Force，暴力匹配算法字符串A中查找字符串B 主串：A，长度n 模式串：B，长度m

女爷i/ 2023年06月23日 02:56/ 0 赞/ 120 阅读

相关字符串匹配算法基础版

最近小谭又被问了一个问题，编程语言中的字符串匹配函数是怎么实现的，是啥原理。看来大猫又要展示他靠才华吃面的大招了。小谭一边心里犯嘀咕，这还能有啥原理，直接用不就行了，管

冷不防/ 2022年10月01日 06:48/ 0 赞/ 99 阅读

相关字符串匹配算法(KMP)

1、BF算法 BF算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等

我不是女神ヾ/ 2022年08月27日 08:57/ 0 赞/ 218 阅读

相关字符串匹配算法

字符串匹配算法本文转自：[Yushneng][Yushneng] ：[http://blog.rainy.im/2016/04/24/string-find/][h

╰半夏微凉°/ 2022年08月21日 08:42/ 0 赞/ 145 阅读

相关字符串匹配算法

记录两个字符串匹配算法：KMP和BM算法。转载地址：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%

╰+攻爆jí腚メ/ 2022年06月16日 09:27/ 0 赞/ 183 阅读

相关算法—KMP字符串匹配

算法—KMP字符串匹配现在有一个问题，要从一个字符串中查找出指定子串的位置(初始下标)，通常地，我们会使用朴素的字符串匹配算法，如下面这道题给出主串和需要查找

短命女/ 2022年05月16日 01:39/ 0 赞/ 481 阅读

相关 KMP字符串匹配算法

写在前面 KMP算法典型例题输入第一行一个整数N，表示测试数据组数。接下来的N\2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，

约定不等于承诺〃/ 2022年05月10日 02:10/ 0 赞/ 304 阅读

相关字符串匹配算法kmp

问题:给定原串origin,求target 串在原串第一次出现的位置,若不存在,输出-1 例如: origin:abcdef target:bc 输出:1 朴素

不念不忘少年蓝@/ 2022年03月22日 07:22/ 0 赞/ 286 阅读

相关字符串匹配算法KMP

KMP算法的原理，这里我不写，建议参考： [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80

╰+攻爆jí腚メ/ 2022年01月14日 00:41/ 0 赞/ 347 阅读

相关字符串匹配算法

BF算法（Brute Force）暴力匹配算法，在主串和模式串每次比较都只前进一个位置，进行比较。 ![18721752-e54c845998d33231.png][

电玩女神/ 2021年10月01日 09:16/ 0 赞/ 384 阅读