KMP算法原理原来这么简单

这篇具有很好参考价值的文章主要介绍了KMP算法原理原来这么简单。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

我觉得这句话说的很好:
kmp算法关键在于:在当前对文本串和模式串检索的过程中,若出现了不匹配,如何充分利用已经匹配的部分,来继续接下来的检索。


暴力解决字符串匹配

KMP算法原理原来这么简单
暴力解法就是两层for循环,每次都一对一的匹配,如果匹配错误就文本串开始位置加1,继续下一次


前缀表的作用

前缀表的作用就是当前位置匹配失败之后,通过前缀表记录的数字来去找到模式串中最合适的位置去重新开始下一次匹配,也就是说,匹配到当前位置失败,通过前缀表跳到前面位置继续匹配。

KMP算法原理原来这么简单
我们一个一个匹配,如果出现不匹配,这时候我们希望通过已经匹配过的字符串,找到其相同的前缀与后缀,来继续接下来的匹配。
KMP算法原理原来这么简单
那我们该如何去计算这个前缀字串与后缀字串在每个位置的最大值,来去继续模式串匹配呢?就是接下来的前缀表的计算(也就是很多KMP算法中next数组的计算)


前缀表的计算(next数组计算)

  • 什么是前缀?
    前缀就是一个字符串不包括最末尾的字符从第一个开始的所有连续字串
    主串:aabaac
    前缀:a 、aa 、aab 、aaba 、aabaa
  • 什么是后缀?
    后缀就是一个字符串不包含第一个字符,每次以末尾结尾的连续字串
    主串:aabaac
    后缀:c 、ac 、aac 、baac 、abaac
  • 如何计算前缀表?
    KMP算法原理原来这么简单

如何使用前缀表?

KMP算法原理原来这么简单
在KMP算法中,一般的next数组会直接使用前缀表,也可能在前缀表的基础上改进一点,但是最终的思路都是围绕前缀表展开,比如有些实现方法是把前缀表统一减一或者整体右移一位,初始位为-1。

时间复杂度:主串与模式串匹配过程最多为O(N),模式串的next数组生成为O(M),所以最后的时间复杂度可以为O(N+M),相较于暴力写法的O(N*M),KMP算法还是极大的提高了检索的效率。

构造next数组

构造next数组其实就是计算模式串s,前缀表的过程。 主要有如下三步:

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况

初始化:
定义两个指针i和j,j指向前缀末尾位置,i指向后缀末尾位置。
然后还要对next数组进行初始化赋值,如下:

int j = -1;
next[0] = j;

处理前后缀不相同的情况:
因为j初始化为-1,那么i就从1开始,进行s[i] 与 s[j+1]的比较。
所以遍历模式串s的循环下标i 要从 1开始,代码如下:

for (int i = 1; i < s.size(); i++) {

如果 s[i] 与 s[j+1]不相同,也就是遇到 前后缀末尾不相同的情况,就要向前回退。next[j]就是记录着j(包括j)之前的子串的相同前后缀的长度。那么 s[i] 与 s[j+1] 不相同,就要找 j+1前一个元素在next数组里的值(就是next[j])。
回退代码:

while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
    j = next[j]; // 向前回退
}

处理前后缀相同的情况
如果 s[i] 与 s[j + 1] 相同,那么就同时向后移动i 和j 说明找到了相同的前后缀,同时还要将j(前缀的长度)赋给next[i], 因为next[i]要记录相同前后缀的长度。

if (s[i] == s[j + 1]) { // 找到相同的前后缀
    j++;
}
next[i] = j;

构建next数组最终代码:

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j(前缀的长度)赋给next[i]
    }
}

本文主要是看了代码随想录的有感理解+画图🚀🚀

KMP算法题目:leetcode -28

28.找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。

示例 1:

输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。文章来源地址https://www.toymoban.com/news/detail-420640.html

class Solution {
public:
    void Getnext(string s, vector<int>& next)
    {
        int j=0;
        next[j]=0;
        for(int i=1;i<next.size();i++)
        {
            while(j>0 && s[i]!=s[j])
            {
                j=next[j-1];
            }
            if(s[i]==s[j])
            {
                j++;
            }
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        vector<int> next(needle.size(),0);
        Getnext(needle,next);
        int j=0;
        for(int i=0;i<haystack.size();i++)
        {
            while(j>0 && haystack[i] != needle[j])
            {
                j=next[j-1];
            }
            if(haystack[i]==needle[j])
            {
                j++;
            }
            if(j==needle.size())
            {
                return i-needle.size()+1;
            }
        }
        return -1;        
    }
};

到了这里,关于KMP算法原理原来这么简单的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 央视的《AI我中华》宣传视频,原来这么简单?

    前段时间,央视的《爱我中华》AI宣传短片火爆全网,有一个穿越转场效果非常惊艳! 今天就先来详细讲解,如何利用Stable Diffusion制作这样的穿越转场视频。 用到的扩展插件就是大名鼎鼎的Deforum,其实很早以前很火的“瞬息全宇宙”视频也是用它来完成的。 需要AI绘画素材

    2024年04月26日
    浏览(38)
  • 原来Vinted注册这么简单!Vinted注册保姆级教程分享

    如果是日本的二手平台代表是煤炉,美国是PoshMark,那欧洲呼声最高的就是Vinted了,今天东哥就给大家科普一下Vinted这个平台,教大家怎么去成功注册Vinted,开启自己的Vinted跨境电商之旅。 Vinted跟煤炉、某鱼差不多性质,是一个二手服装商品和配饰的平台,支持在 iOS、Andr

    2024年02月09日
    浏览(50)
  • python轻量级web框架flask初探,搭建网站原来这么简单

    ✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN新星创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开

    2024年03月19日
    浏览(125)
  • KMP算法的及其原理

     KMP算法 首先 我们先了解一下 KMP算法的作用 str1 和str2 字符串 如果str1中包含str2 那么返回头位置 如果不包含返回-1 首先 我们先加入一个概念: 有一个next数组 next[i]的值为 str2 中 以i-1位置为结尾的字符串中 最长相同前缀后缀为多长(相同前缀后缀 不是对称  aba 中

    2024年02月15日
    浏览(52)
  • 【算法 - 动态规划】原来写出动态规划如此简单!

    从本篇开始,我们就正式开始进入 动态规划 系列文章的学习。 本文先来练习两道通过 建立缓存表 优化解题过程的题目,对如何将 递归函数 修改成 动态规划 的流程有个基本的熟悉。 用最简单的想法完成题目要求的 递归 函数; 定义明确 递归函数 的功能!!! 分析是否存

    2024年02月21日
    浏览(47)
  • 物联网网关,原来是这么回事,感谢!

    《高并发系统实战派》-- 你值得拥有 物联网网关是连接物联网设备和互联网的重要桥梁,它负责将物联网设备采集到的数据进行处理、存储和转发,使其能够与云端或其他设备进行通信。物联网网关的作用是实现物联网设备与云端的无缝连接和数据交换。 不要物联网网关行

    2024年02月08日
    浏览(49)
  • 数据结构-串-KMP算法详解(Next数组计算)(简单易懂)

    本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了) 为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼 提示:以下信息来源百度 KMP算法是一种改进的字符串匹配算法,由D.E.K

    2024年02月06日
    浏览(45)
  • 原来服务器这么有用-Docker安装

    在此之前青阳通过各种方式介绍过自己通过服务器搭建的一些玩法,也写过一些教程,但是那些教程,现在回头来看,都是有些杂乱了,统一性不强。我就准备重新整理一下之前写的文章,并且准备重新开一个专题来写自己折腾的内容,专题的名字就叫-原来服务器这么有用。

    2024年02月04日
    浏览(67)
  • 原来.NET写的Linux桌面这么好看?

    本文将讲解如何使用 Blazor 运行跨平台应用,应用到的技术有以下几点 Blazor Masa Blazor Photino.Blazor Ubuntu 用于验证跨平台性,并且是否提高开发效率,Blazor和Photino一块使用的技术称为 Blazor Hybrid , Blazor是一种使用.NET和C#构建客户端Web应用程序的新兴技术。它允许开发者在浏览器

    2024年02月05日
    浏览(48)
  • Python制作进度条,原来有这么多方法

    如果你之前没用过进度条,八成是觉得它会增加不必要的复杂性或者很难维护,其实不然。要加一个进度条其实只需要几行代码。 在这几行代码中,我们可以看看如何在命令行脚本以及 PySimpleGUI UI 中添加进度条。 下文将介绍 4 个常用的 Python 进度条库: 第一个要介绍的 Py

    2024年02月08日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包