字符串匹配算法之 Kmp 算法

本贴最后更新于 1534 天前,其中的信息可能已经沧海桑田

KMP 算法核心思路

kmp 算法也是一种字符串匹配算法,但是他和 BM 算法不同的是,从前往后开始匹配。共同点是都是想找出滑动最大位数的规律。

假设现在有两个字符串,一个是 abaabaabbabaaabaabbabaab,起个名叫 m,另一个 abaabbabaab 叫 p,
企业微信截图 7a2234afd6e34b9b96834a0f40ad5c44.png
两个字符串从头开始匹配的,匹配到第六个字符的时候出现不匹配的情况,这个时候把主串的第六位字符叫做坏字符,前面匹配到的叫做好前缀,这两个称呼都是针对主串的。当出现不匹配的坏字符的时候,模式串滑动多少位,能够更快的匹配完?

KMP 算法就是在视图寻找一种规律,在模式传和主串匹配的过程中,当遇到坏字符后,能否找到一种规律,将模式串一次性滑动很多位,而且匹配的字符尽可能的不再匹配。

观察主串的好前缀其实也是模式串的前缀子串,我们只要找出公共的子串,公共子串同时也是后缀子串,就可以确定滑动的位数,以上面的两个字符串为例,最长的公共子串是 ab,长度为 2,坏字符的索引是 5,将模式串滑动到公共子串的位置所需滑动的位数 5-2=3,如下图:
企业微信截图 89a59767c9d64a48a6dfbe126d2bb17f.png
这个时候需要重新,模式串中坏字符对应指针的位置,这个新位置是在好前缀公共子串的后面,也就是 公共子串最后一位字符的索引 +1.

假设坏字符对应主串的位置是 i,在模式串的位置是 j,最长公共子串,就是模式串 p[0]到 p[j]之间子串的,前缀和后缀的最长公共子串。那我们是不是可以对每个位置的模式串子串求最长公共子串,然后把它存到数组里,当主串和模式串匹配到坏字符的时候,直接从数组中取出最长公共子串,然后就可以得出滑动的位数了。

那我们来看下一下这个数组是如何构造的以及都有什么特征。

数组的值存储的是,最长可匹配前缀子串的结尾字符的下标,这里我们前缀子串和后缀子串去最长数组的下标是每个前缀子串的下标

模式字符串 a b a b a c d

模式串前缀 前缀子串结尾字符下标 最长可匹配前缀子串结尾字符下标 next 值
a 0 -1(表示不存在) next[0] = -1
a b 1 -1 next[1] = -1
a b a 2 0 next[2] = 0
a b a b 3 1 next[3] = 1
a b a b a 4 2 next[4] = 2
a b a b a c 5 -1 next[5] = -1

代码实现

public class Kmp {
    /**
     * next的数组推到过程是假设已经有部分数据计算出来,以此为基础计算后面的
     * 这里说的最公共子串,指的是,模式串从开头到当前位置的子串的所有前缀子串和后缀子串的最长公共子串
     * <p>
     * 假设模式串中0-9位对应的公共最长子串已经计算出来,此时要计算第10位字符'a'对应的最大公共子串长度
     * 首先考虑加了一个字符,最大公共子串长度是否会加一,这个时候可以利用已经求出的第9位的最大公共子串,
     * 假设第九位最大公共子串是abaa,此时看这个前缀子串的后面一个字符是否和新字符'a'相等,如果相等,那最长公共子串长度就+1
     * <p>
     * 如果不相等,就只能考虑最长长度不变或者减小的情况了。
     * 此时要找的是,最大前缀的前缀和最大后缀加'a'字符组合的后缀的公共最长的子串了,
     * <p>
     * 最长前缀和最长后缀是一样的,那么问题就转换成,最长前缀加新字符的公共最长的子串了,就又回到了开始时的规则了
     * <p>
     * 整体解决思路类似于一个动态规划的问题,求某个位置的所有前缀子串和所有后缀子串的公共子串长度,
     * 可以通过前一个位置的公最长共子串长度得出。
     *
     * @param b
     * @param m
     * @return
     */
    public static int[] getNexts(char[] b, int m) {
        int[] next = new int[m];
        next[0] = -1;
        int j = -1;
        for (int i = 1; i < m; i++) {
            while (b[i] != b[j + 1] && j >= 0) {
                j = next[j];
            }
            // 如果i位置的字符和最大前缀子串的后面一个字符相等,那么i位置的最大前缀子串长度就+1
            if (b[i] == b[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    /**
     * next 数组存的是当前
     * 从模式串头部到当前位置的这一子串的,
     * 所有前缀子串和所有后缀子串匹配到最长公共子串时
     * 前缀子串的最后一个字符的索引
     *
     * @param a
     * @param n
     * @param b
     * @param m
     * @return
     */
    public static int kmp(char[] a, int n, char[] b, int m) {
        int[] next = getNexts(b, m);
        // i 是主串指针,j是模式串指针
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && b[j] != a[i]) {
                j = next[j - 1] + 1;
            }
            if (a[i] == b[j]) {
                j++;
            }

            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

}

实力有限,如果看不懂我说的呢,就给大家推荐知乎上的一个问答,里面说的很是通俗易懂如何更好的理解和掌握 KMP 算法?前三个回答强烈建议大家细读细品。

  • 字符串
    28 引用 • 57 回帖
  • 算法
    388 引用 • 254 回帖 • 22 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • Quicker

    Quicker 您的指尖工具箱!操作更少,收获更多!

    16 引用 • 68 回帖
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    129 引用 • 793 回帖 • 1 关注
  • 锤子科技

    锤子科技(Smartisan)成立于 2012 年 5 月,是一家制造移动互联网终端设备的公司,公司的使命是用完美主义的工匠精神,打造用户体验一流的数码消费类产品(智能手机为主),改善人们的生活质量。

    4 引用 • 31 回帖 • 5 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • 深度学习

    深度学习(Deep Learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    40 引用 • 40 回帖
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    70 引用 • 532 回帖 • 706 关注
  • Swagger

    Swagger 是一款非常流行的 API 开发工具,它遵循 OpenAPI Specification(这是一种通用的、和编程语言无关的 API 描述规范)。Swagger 贯穿整个 API 生命周期,如 API 的设计、编写文档、测试和部署。

    26 引用 • 35 回帖 • 7 关注
  • OnlyOffice
    4 引用 • 19 关注
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 405 关注
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 316 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    20 引用 • 245 回帖 • 232 关注
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 381 关注
  • 创业

    你比 99% 的人都优秀么?

    82 引用 • 1397 回帖
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 42 关注
  • 分享

    有什么新发现就分享给大家吧!

    240 引用 • 1729 回帖
  • Linux

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

    914 引用 • 930 回帖
  • 心情

    心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。

    59 引用 • 369 回帖
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖 • 7 关注
  • 阿里云

    阿里云是阿里巴巴集团旗下公司,是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务,以及大数据、人工智能服务、精准定制基于场景的行业解决方案。

    89 引用 • 345 回帖
  • Gitea

    Gitea 是一个开源社区驱动的轻量级代码托管解决方案,后端采用 Go 编写,采用 MIT 许可证。

    4 引用 • 16 回帖 • 6 关注
  • CSDN

    CSDN (Chinese Software Developer Network) 创立于 1999 年,是中国的 IT 社区和服务平台,为中国的软件开发者和 IT 从业者提供知识传播、职业发展、软件开发等全生命周期服务,满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。

    14 引用 • 155 回帖
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    330 引用 • 614 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 33 关注
  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 255 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    18150 引用 • 66975 回帖
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖 • 3 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    215 引用 • 462 回帖