字符串匹配算法之 BF 算法和 RK 算法

本贴最后更新于 2015 天前,其中的信息可能已经时移俗易

BF 算法

BF 是 Brute Force 的缩写,叫做暴力匹配算法,由名字就能看得出来,真的很暴力 😃,暴力的一般都是头脑简单四肢发达,时间复杂度比较高的那种。那我们就来看看究竟有多暴力吧!
在字符串匹配中有两个概念,煮串,不对,是主串和模式串,比如说有两个字符串 A、B,需求是要在字符串 A 中查找字符串 B,那么 A 就是主串,B 就是模式串。

BF 算法的脑回路是,主串和模式串从头部字符开始匹配,如果发现有匹配的,那模式串就向右移动一位,继续按照前面的规则匹配,至到能匹配到,匹配过程大致和下面类似:

image.png

是不是很暴力啊,想都不用想,实现方式里一定有两个循环,时间复杂度想都不用想,应该挺高的吧,那我们来分析一下。假设主串和模式串的长度分别是 n 和 m,根据上面的匹配过程我们可以分析出整个过程需要匹配 n-m+1 次,每次要进行 m 次的比对,那总共就需要(n-m+1) * m 比对,时间复杂度是 O(n*m)的,这要是字符串长度比较大的话,那就挂了哇。但是,在时间软件开发中确实比较常用的呢,难道是我们都傻了么,明明那么慢的算法,还用。有天有个大牛告诉我,现实不是这样的,而是这样的,

  • 实际的软件开发中,大部分情况下,模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候,当中途遇到不能匹配的字符的时候,就可以就停止了,不需要把 m 个字符都比对一下。所以,尽管理论上的最坏情况时间复杂度是 O(n*m),但是,统计意义上,大部分情况下,算法执行效率要比这个高很多
  • 就是因为简单呀,当然是在满足性能要求条件下的话,简单就是最好的。

简单实现一下就是下面的喽:

public static int bF(String mainStr, String matStr) { int n = mainStr.length(), m = matStr.length(), k; if (m > n) { return -1; } char[] mainChars = mainStr.toCharArray(); char[] matChars = matStr.toCharArray(); // 外层循环控制向右滑动次数,i记录滑动位置 for (int i = 0; i <= n - m; i++) { // k记录在一次比较过程中相等字符的个数 k = 0; for (int j = 0; j < m; j++) { if (mainChars[i + j] == matChars[j]) { k++; } else { // 在一次比较过程中,如果有不相等的字符,就结束后次轮的比较,滑动进行下一轮的比较 break; } } // 判断再一次比较完结束后,相等字符的个数是否和模式串的个数相等,如果相等就说明匹配到了, // 如果不相等,就向右滑动,进行下一轮比较 if (k == m) { return i; } } return -1; }

RK 算法

全称叫 Rabin-Karp 算,两个人名字的结合,诞生的。。
在 BF 算法中,其实就是取主串的 n-m+1 个子串和模式串进行一一比对,主要消耗就集中在子串和模式串挨个字符的比较,如果每个字符都计算一个固定的值,再和模式串使用同种方式计算的值进行比较,那就很快乐了。
RK 算法的核心思路: 通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了。
来看一下 java.utils.String 中计算 hash 值是如何做的,

public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

它要遍历每个字符来计算 hash 值,虽然通过计算 hash 值提高了比较效率,但是计算 hash 值的代价也挺高呀,看起来效率也没提升呀,不急呀,这里就要设计其他的 hash 函数了。
要处理的字符串就只包含 a~z 这 26 个小写字母,那就用二十六进制来表示一个字符串。把 a~z 这 26 个字符映射到 0~25 这 26 个数字,a 就表示 0,b 就表示 1,以此类推,z 表示 25。来看一下十进制和二十六进制计算值的方式

image.png

那一个 m 长度的 adf...gaf 字符串的 hash 值就是

image.png

只要事先计算好这些 26^(m-1)的值,那就可以大幅度提高效率。

public static int rK(String mainStr, String matStr) { int m = mainStr.length(), n = matStr.length(), s, j; int[] hash = new int[m - n + 1]; int[] table = new int[26]; char[] a1 = mainStr.toCharArray(); char[] b1 = matStr.toCharArray(); s = 1; //将26的次方存储在一个表里,取的时候直接用 for (j = 0; j < 26; j++) { table[j] = s; s *= 26; } for (int i = 0; i <= m - n; i++) { s = 0; for (j = 0; j < n; j++) { s += (a1[i + j] - 'a') * table[n - 1 - j]; } hash[i] = s; } s = 0; for (j = 0; j < n; j++) { s += (b1[j] - 'a') * table[n - 1 - j]; } for (j = 0; j < m - n + 1; j++) { if (hash[j] == s) { return j; } } return -1; }

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    2 引用 • 14 回帖 • 3 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 647 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 710 关注
  • 叶归
    13 引用 • 59 回帖 • 22 关注
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖 • 4 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 143 回帖
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖 • 1 关注
  • Access
    1 引用 • 3 回帖
  • PWA

    PWA(Progressive Web App)是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术,在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 184 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    591 引用 • 3528 回帖 • 1 关注
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 105 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 15 关注
  • 链滴

    链滴是一个记录生活的地方。

    记录生活,连接点滴

    183 引用 • 3885 回帖
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 2 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    118 引用 • 54 回帖 • 5 关注
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    201 引用 • 120 回帖 • 3 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 766 关注
  • 旅游

    希望你我能在旅途中找到人生的下一站。

    100 引用 • 905 回帖
  • Linux

    Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。

    955 引用 • 944 回帖 • 1 关注
  • Solo

    Solo 是一款小而美的开源博客系统,专为程序员设计。Solo 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    1444 引用 • 10083 回帖 • 507 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    188 引用 • 1057 回帖
  • BAE

    百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。

    19 引用 • 75 回帖 • 681 关注
  • 996
    13 引用 • 200 回帖 • 1 关注
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    59 引用 • 22 回帖 • 6 关注
  • 自由行
    1 关注
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    77 引用 • 37 回帖