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

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

目录

---

🌞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>
#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 tlen=t.length();
    int slen=s.length();

    int *next=new int[tlen];
    getNext(t,next);

    int i=0,j=0;
    while(i<slen && j<tlen){
        if(j==-1 || s[i]==t[j]){
            i++;
            j++;
        }
        else{
            j=next[j];
        }
    }
    delete [] next;
    
    if(j>=tlen) return (i-tlen);
    else return (-1);
}

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

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

    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;
}