个人主页：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
#include
using namespace std;
int BF(string s,string t){
int i=0,j=0;
while(i 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< return 0; } 2.2 KMP算法 基本步骤： 构建部分匹配表： KMP算法的核心是在匹配失败时能够利用已匹配的信息，避免重复比较。 匹配过程： 在匹配过程中，通过部分匹配表的信息来实现跳过一定的比较。 注意：不要直接使用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 if(s[i]==t[j]){ i++;j++; } else{ i=i-j+1; j=0; } } if(j>=tlen) cout<<"暴力搜索模式匹配成功,"< else cout<<"暴力搜索模式匹配失败"< } //方法二：KMP算法 void getNext(string t,int *next){ int j=0,k=-1; next[0]=-1; while(j 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 if(j==-1 || s[i]==t[j]){ i++;j++; } else j=next[j]; } delete [] next; if(j>=tlen) cout<<"KMP算法模式匹配成功,"< else cout<<"KMP算法模式匹配失败"< } 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 解决方案： int slen=s.length(); for(int i=0;i 上述用例我相信很多人经常这样用却并没有出错，但是在下面的案例错误就十分明显。因为在 测试用例【1为目标串，2为模式串】 helloworldwo 中返回的【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 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 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< return 0; } 参考链接
发表评论