🌈个人主页:Sarapines Programmer
🔥 系列专栏:《数据结构奇遇记》
🔖墨香寄清辞:墨痕寄壮志,星辰梦未满。 通幽径心凝意,剑指苍穹势如山。
目录
🌞1. 模式匹配的基本概念
🌞2. 模式匹配的解决办法
🎈2.1 暴力匹配(BF)算法
🎈2.2 KMP算法
🤖2.3 BUG记录_KMP算法
🌞1. 模式匹配的基本概念
1.1 模式匹配是在字符串 s (称为目标串)中寻找字符串 t (称为模式串)的过程。
目标串: 这是要进行搜索的字符串,包含了我们需要查找模式的信息。
模式串: 这是要在文本串中寻找的具体字符串或子字符串。
示例:目标串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算法
基本步骤:
构建部分匹配表: KMP算法的核心是在匹配失败时能够利用已匹配的信息,避免重复比较。
匹配过程: 在匹配过程中,通过部分匹配表的信息来实现跳过一定的比较。
注意:不要直接使用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为模式串】
- helloworld
- 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;
}
文章来源:https://www.toymoban.com/news/detail-762405.html
文章来源地址https://www.toymoban.com/news/detail-762405.html
到了这里,关于【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!