【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现

这篇具有很好参考价值的文章主要介绍了【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现,# 数据结构基础强化,数据结构,算法,c语言,KMP,模式匹配,暴力搜索

🌈个人主页:Sarapines Programmer
🔥 系列专栏:《数据结构奇遇记》
🔖墨香寄清辞:墨痕寄壮志,星辰梦未满。 通幽径心凝意,剑指苍穹势如山。

【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现,# 数据结构基础强化,数据结构,算法,c语言,KMP,模式匹配,暴力搜索

目录


🌞1. 模式匹配的基本概念

🌞2. 模式匹配的解决办法

🎈2.1 暴力匹配(BF)算法

🎈2.2 KMP算法

🤖2.3 BUG记录_KMP算法


🌞1. 模式匹配的基本概念

1.1 模式匹配是在字符串 s (称为目标串)中寻找字符串 t (称为模式串)的过程。

  1. 目标串: 这是要进行搜索的字符串,包含了我们需要查找模式的信息。

  2. 模式串: 这是要在文本串中寻找的具体字符串或子字符串。

示例:目标串s="aaaaab",模式串t="aaab".

1.2 常见的模式匹配算法

  • 暴力匹配(BF)算法: 从文本串的第一个字符开始,逐一与模式串比较,如果不匹配,则移动到下一个位置。

  • KMP算法: 通过预处理模式串,构建一个部分匹配表next[],利用已匹配的信息来避免不必要的比较,提高匹配效率。


🌞2. 模式匹配的解决办法

🎈2.1 暴力匹配(BF)算法

从头开始遍历寻找,若不匹配则主串的指针i返回,从下一个地址开始(i-j+1)

简单示例:目标串s="aaaaab",模式串t="aaab".若成功返回匹配成功的位置,否则返回0.

#include <iostream>
#include <string>
using namespace std;

int BF(string s,string t){
    int i=0,j=0;
    while(i<s.length() && j<t.length()){
        if(s[i]==t[j]){
            i++;
            j++;
        }
        else{
            i=i-j+1;
            j=0;
        }
    }
    if(j>=t.length()) return (i-t.length());
    else return (-1);
}

int main(){
    string s1,s2;
    getline(cin,s1);//helloworld
    getline(cin,s2);//wo

    cout<<BF(s1,s2)<<endl;

    return 0;
}

🎈2.2 KMP算法

基本步骤:

  1. 构建部分匹配表: KMP算法的核心是在匹配失败时能够利用已匹配的信息,避免重复比较。

  2. 匹配过程: 在匹配过程中,通过部分匹配表的信息来实现跳过一定的比较。

注意:不要直接使用str.length()    做个转换再用  int slen=str.length();

简单示例:目标串s="aaaaab",模式串t="aaab".若成功返回匹配成功的位置,否则返回0.

#include <iostream>

using namespace std;

/********模式识别**********/
//方法一:暴力搜索
void BF(string s,string t){
    int i=0,j=0;
    int slen=s.length(),tlen=t.length();

    for(;i<slen && j<tlen;){
        if(s[i]==t[j]){
            i++;j++;
        }
        else{
            i=i-j+1;
            j=0;
        }
    }

    if(j>=tlen) cout<<"暴力搜索模式匹配成功,"<<t<<"处于"<<s<<"的第"<<i-tlen+1<<"位"<<endl;
    else cout<<"暴力搜索模式匹配失败"<<endl;
}

//方法二:KMP算法
void getNext(string t,int *next){
    int j=0,k=-1;
    next[0]=-1;
    while(j<t.length()){
        if(k==-1 || t[k]==t[j]){
            j++;k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

void KMP(string s,string t){
    int slen=s.length(),tlen=t.length();
    int i=0,j=0;

    int *next=new int[tlen];
    getNext(t,next);
    while(i<slen && j<tlen){
        if(j==-1 || s[i]==t[j]){
            i++;j++;
        }
        else j=next[j];
    }
    delete [] next;
    if(j>=tlen) cout<<"KMP算法模式匹配成功,"<<t<<"处于"<<s<<"的第"<<i-tlen+1<<"位"<<endl;
    else cout<<"KMP算法模式匹配失败"<<endl;
}

int main(){
    string s,t;
    getline(cin,s);
    getline(cin,t);

    //暴力搜索
    BF(s,t);

    //KMP
    KMP(s,t);
    return 0;
}

🤖2.3 BUG记录_KMP算法

千万不要小看一个小小的bug会毁我大几小时的宝贵时光!!!

错误示例:
for(int i=0;i<s.length();i++){...}//s为string类型

解决方案:
int slen=s.length();
for(int i=0;i<slen;i++){...}

上述用例我相信很多人经常这样用却并没有出错,但是在下面的案例错误就十分明显。因为在

测试用例【1为目标串,2为模式串】

  1. helloworld
  2. wo

中返回的【i-t.length()】值一个为 0 (显然是错的),一个为 5.

【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现,# 数据结构基础强化,数据结构,算法,c语言,KMP,模式匹配,暴力搜索

错误示例:【正确示例见章节2.2】

#include <iostream>
#include <string>
using namespace std;

/*KMP算法*/
//求next[]
void getNext(string t,int next[]){
    int j=0,k=-1;//j扫描t,k记录t[j]之前与t首字符相同的个数
    next[0]=-1;
    for(;j<t.length();){//next[0]已经给了,剩下的t.length()-1
        if(k==-1 || t[j]==t[k]){
            j++;k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

//KMP
int KMP(string s,string t){
    int *next=new int[t.length()];
    getNext(t,next);

    int i=0,j=0;
    while(i<s.length() && j<t.length()){
        if(j==-1 || s[i]==t[j]){
            i++;
            j++;
        }
        else{
            j=next[j];
        }
    }

    delete [] next;
    
    if(j>=t.length()) return (i-t.length());
    else return (-1);
}

int main(){
    string s1,s2;
    getline(cin,s1);//helloworld
    getline(cin,s2);//wo

    cout<<KMP(s1,s2)<<endl;

    return 0;
}

【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现,# 数据结构基础强化,数据结构,算法,c语言,KMP,模式匹配,暴力搜索

【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现,# 数据结构基础强化,数据结构,算法,c语言,KMP,模式匹配,暴力搜索文章来源地址https://www.toymoban.com/news/detail-762405.html

到了这里,关于【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(72)
  • 数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】

    💂 个人网站:  路遥叶子 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主 💬 如果文章对你有帮助、 欢迎 关注、点赞、收藏 (一键三连)和订阅专栏哦 💅  想寻找共同成长的小伙伴,请点击【 Java全栈开发社区 】

    2023年04月16日
    浏览(41)
  • 数据结构课设:基于字符串模式匹配算法的病毒感染检测问题

    1.掌握字符串的顺序存储表示方法。 2.掌握字符串模式匹配算法BF算法或KMP算法的实现。 问题描述 医学研究者最近发现了某些新病毒,通过对这些病毒的分析,得知它们的DNA序列都是环状的。现在研究者已收集了大量的病毒DNA和人的DNA数据,想快速检测出这些人是否感染了

    2023年04月27日
    浏览(48)
  • 【数据结构与算法】KMP算法

     在C语言的strstr的实现过程中,所涉及的算法较为简单,或者说只是一个简单的思路而已,在字符串过长时,所涉及的算法复杂度过大,那有没有比较简单的算法呢?这里就涉及到了KMP——由三位大佬提出的,下面我们一起来了解吧!  KMP算法是一种改进的字符串匹配算法

    2024年03月26日
    浏览(48)
  • 数据结构--KMP算法

    模板: 例题:acwing--kmp字符串(831. KMP字符串 - AcWing题库) 给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。 模式串 P 在字符串 S 中多次作为子串出现。 求出模式串 P 在字符串 S 中所有出现的位置的起始下标。 输入格式 第一

    2024年02月11日
    浏览(40)
  • 数据结构:KMP算法

         KMP算法是由Knuth、Morris和Pratt三位学者发明的,所以取了三位学者名字的首字母,叫作KMP算法。      KMP主要用于字符串匹配的问题,主要思想是 当出现字符串不匹配时,我们可以知道一部分之前已经匹配过的的文本内容,利用这些信息从而避免从头再开始匹配。    

    2024年02月04日
    浏览(43)
  • 数据结构KMP算法详解

    目录 1. KMP算法是什么? 2. KMP算法的由来 2.1 需要要解决的问题 2.2 一开始想到的方法 2.3 KMP算法诞生了 3.KMP算法的详解 4.KMP算法的实现 5.KMP算法的改进 KMP算法是一种改进的字符串匹配算法,即可以 快速的从主串中找到子串的算法 ,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人

    2024年02月12日
    浏览(57)
  • [数据结构] 串与KMP算法详解

    今天是农历大年初三,祝大家新年快乐! 尽管新旧交替只是一个瞬间,在大家互祝新年快乐的瞬间,在时钟倒计时数到零的瞬间,在烟花在黑色幕布绽放的瞬间,在心底默默许下愿望的瞬间……跨入新的一年,并不意味了一切都会朝着更美好,也没有什么会从天而降,我们赋

    2024年02月19日
    浏览(40)
  • C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化

      D.E.Knuth   J.H.Morris KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。 KMP算法由 D.E.Knuth , J.H.Morris 和 V.R.Pratt 在 Brute-Force 算法的基础上提出的模式匹配的改进算法。因此人们称它为“克努特—莫里斯—普拉特算法”,简称KMP算法。K

    2024年01月25日
    浏览(51)
  • 数据结构--字符串的KMP算法

    朴素模式匹配算法: 一旦发现当前这个子串中某个字符不匹配,就只能转而匹配下一个子串(从头开始) 但我们可以知道: 不匹配的字符之前,一定是和模式串一致的 color{red}不匹配的字符之前,一定是和模式串一致的 不匹配的字符之前,一定是和模式串一致的 我们可以利用

    2024年02月12日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包