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

目录


1. 模式匹配的基本概念

2. 模式匹配的解决办法

2.1暴力匹配(BF)算法

2.2KMP算法

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 #include using namespace std;int BF(string s,string t){int i=0,j=0;while(i<s.length() && j=t.length()) return (i-t.length());else return (-1);}int main(){string s1,s2;getline(cin,s1);//helloworldgetline(cin,s2);//wocout<<BF(s1,s2)<<endl;return 0;}

2.2KMP算法

基本步骤:

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

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

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

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

#include 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) 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) 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);//KMPKMP(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 #include 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()-1if(k==-1 || t[j]==t[k]){j++;k++;next[j]=k;}else k=next[k];}}//KMPint 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()) return (i-t.length());else return (-1);}int main(){string s1,s2;getline(cin,s1);//helloworldgetline(cin,s2);//wocout<<KMP(s1,s2)<<endl;return 0;}