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

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



🌞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.

错误示例:【正确示例见章节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;
}

相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
目录
相关文章
|
11天前
|
机器学习/深度学习 安全 算法
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
|
26天前
|
存储 算法 C++
【C/C++ 数据结构 】无向图和有向图的差异
【C/C++ 数据结构 】无向图和有向图的差异
25 0
|
26天前
|
存储 算法 Serverless
【C/C++ 数据结构】深入探索数据结构中算法复杂度:从C++和数学的视角
【C/C++ 数据结构】深入探索数据结构中算法复杂度:从C++和数学的视角
46 0
|
11天前
|
C++
glog --- C++日志库
glog --- C++日志库
|
11天前
|
算法 测试技术 C#
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
|
11天前
|
算法 测试技术 Serverless
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
|
11天前
|
算法 测试技术 C#
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
|
26天前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
11 0
|
26天前
|
存储 算法 数据库
【C/C++ 数据结构 】树的 四种表示方法
【C/C++ 数据结构 】树的 四种表示方法
26 0
|
26天前
|
XML 运维 监控
【深入探究 C++ 日志库清理策略】glog、log4cplus 和 spdlog 的日志文件管理策略
【深入探究 C++ 日志库清理策略】glog、log4cplus 和 spdlog 的日志文件管理策略
63 0