串匹配问题：BF算法、KMP算法、BM算法

常见5种基本匹配算法匹配算法在计算机科学和信息检索领域广泛应用，用于确定两个或多个对象之间的相似度或一致性。

以下是常见的5种基本匹配算法：1.精确匹配算法：精确匹配算法用于确定两个对象是否完全相同。

它比较两个对象的每个字符、字节或元素，如果它们在相同位置上完全匹配，则返回匹配结果为真。

精确匹配算法适用于需要确定两个对象是否完全相同的场景，例如字符串匹配、图像匹配等。

2.模式匹配算法：模式匹配算法用于确定一个模式字符串是否出现在一个文本字符串中。

常见的模式匹配算法有暴力法、KMP算法、BM算法等。

暴力法是最简单的模式匹配算法，它按顺序比较模式字符串和文本字符串的每个字符，直到找到一次完全匹配或结束。

KMP算法通过预处理建立一个跳转表来快速定位比较的位置，减少了无效比较的次数。

BM算法利用模式串的后缀和模式串的字符不完全匹配时在文本串中平移模式串的位置，从而快速定位比较的位置。

3.近似匹配算法：4.模糊匹配算法：5.哈希匹配算法：哈希匹配算法用于确定两个对象之间的哈希值是否相等。

哈希值是通过将对象映射到一个固定长度的字符串来表示的，相同的对象会产生相同的哈希值。

常见的哈希匹配算法有MD5算法、SHA算法等。

哈希匹配算法适用于需要快速判断两个对象是否相等的场景，例如文件的完整性校验、数据校验等。

以上是常见的5种基本匹配算法，它们各自适用于不同的场景和需求，选择合适的匹配算法可以提高效率和准确性，并且在实际应用中经常会结合多种算法来获取更好的匹配结果。

BF算法KMP算法BM算法BF算法（Brute-Force算法）是一种简单直接的字符串匹配算法。

它的基本思想是从主串的第一个字符开始，逐个与模式串的字符进行比较，如果匹配失败，则主串的指针向右移动一位，继续从下一个字符开始匹配。

重复这个过程，直到找到匹配的子串或者主串遍历完毕。

BF算法的时间复杂度是O(n*m)，其中n和m分别是主串和模式串的长度。

当模式串较长时，算法的效率较低。

但是BF算法的实现简单，易于理解，对于较短的模式串和主串，仍然是一种可行的匹配算法。

KMP算法（Knuth-Morris-Pratt算法）是一种改进的字符串匹配算法，它利用了模式串内部的信息，避免了不必要的比较。

KMP算法引入了一个next数组，用于记录模式串中每个位置对应的最长可匹配前缀子串的长度。

KMP算法的基本思想是，当匹配失败时，不是简单地将主串指针右移一位，而是利用next数组将模式串的指针向右移动若干位，使得主串和模式串中已经匹配的部分保持一致，减少比较次数。

通过预处理模式串，计算出next数组，可以在O(n+m)的时间复杂度内完成匹配。

BM算法（Boyer-Moore算法）是一种高效的字符串匹配算法，它结合了坏字符规则和好后缀规则。

BM算法从模式串的末尾开始匹配，根据坏字符规则，如果在匹配过程中发现了不匹配的字符，可以直接将模式串向右滑动到该字符在模式串中最右出现的位置。

BM算法还利用了好后缀规则，当发现坏字符后，可以根据好后缀的位置和模式串的后缀子串进行匹配，从而减少不必要的比较。

通过预处理模式串，计算出坏字符规则和好后缀规则对应的滑动距离，可以在最坏情况下实现O(n/m)的时间复杂度。

总结来说，BF算法是一种简单直接的字符串匹配算法，适用于较短的模式串和主串；KMP算法通过预处理模式串，利用next数组减少比较次数，提高了匹配效率；BM算法结合了坏字符规则和好后缀规则，利用了更多的信息，是一种高效的字符串匹配算法。

Boyer-Moore算法Boyer-Moore算法（简称BM算法）是一种高效的字符串匹配算法，由Robert S. Boyer和J Strother Moore于1977年提出。

相比于其他字符串匹配算法，如Brute-Force算法和KMP算法，BM算法在处理大型文本的匹配问题时具有较低的时间复杂度。

1. 算法原理BM算法的核心思想是从待匹配的字符串的末尾进行比较，而不是从开头。

具体来说，算法首先获取模式串（待搜索的子串）的最后一个字符，然后在待匹配的字符串中以模式串的长度为步长，从后往前进行比较。

如果比较的过程中发现存在不匹配的字符，算法会根据预处理的规则跳过一定范围的字符，从而实现快速的搜索。

而将模式串与待匹配的字符串进行比较的过程中，算法会根据预处理的规则将模式串向后移动一定的位置，以加快搜索的速度。

2. 算法流程BM算法的主要流程可以概括为以下几个步骤：1.预处理模式串：–建立一个坏字符规则表，记录每个字符在模式串中最右出现的位置。

–建立好后缀规则表，记录每个后缀子串在模式串中的出现位置。

2.匹配过程：–从待匹配字符串的末尾与模式串的末尾开始比较。

–如果遇到坏字符（即不匹配的字符），根据坏字符规则表和好后缀规则表进行移动。

–当模式串完全匹配，则表示找到了一个匹配的字符串。

3. 算法优势BM算法在字符串匹配问题中具有较高的效率，其优势主要体现在以下几个方面：•坏字符规则表：BM算法通过预处理模式串，建立坏字符规则表，从而实现在找到不匹配的字符时能够快速将模式串右移，从而跳过一定范围的字符。

这种方式可以大幅减少比较的次数，提高搜索效率。

•好后缀规则表：BM算法还通过预处理模式串，建立好后缀规则表。

当发现不匹配的字符时，算法会根据好后缀规则表的信息将模式串向后移动一定位置，以加快搜索速度。

•时间复杂度低：相比于Brute-Force算法和KMP算法，BM算法在处理大型文本的匹配问题时具有较低的时间复杂度。

本文分为二个部分：第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度，并两相对照各自的匹配原理；第二部分、通过我此前一篇文章的引用，用图从头到尾详细阐述KMP算法中的next数组求法，并运用求得的next数组写出KMP算法的源码。

力求让此文彻底让读者洞穿此KMP算法，所有原理，来龙去脉，让读者搞个通通透透。

在看本文之前，你心中如若对前缀和后缀这个两个概念有自己的理解，便最好了。

有些东西比如此KMP算法需要我们反复思考，反复求解才行。

个人写的关于KMP算法的第二篇文章为：六（续）、从KMP算法一步一步谈到BM算法。

ok，若有任何问题，恳请不吝指正。

多谢。

第一部分、KMP算法初解1、普通字符串匹配BF算法与KMP算法的时间复杂度比较KMP算法是一种线性时间复杂的字符串匹配算法，它是对BF算法（Brute-Force，最基本的字符串匹配算法的）改进。

对于给的原始串S和模式串P，需要从字符串S中找到字符串P出现的位置的索引。

BF算法的时间复杂度O(strlen(S) * strlen(T))，空间复杂度O(1)。

KMP算法的时间复杂度O(strlen(S) + strlen(T))，空间复杂度O(strlen(T))。

2、BF算法与KMP算法的区别假设现在S串匹配到i位置，T串匹配到j位置。

那么总的来说，两种算法的主要区别在于失配的情况下，对的值做的处理（注意，本文中的字符串下标都是从0开始计算）：BF算法中，如果当前字符匹配成功，即s[i+j] == T[j]，令j++，继续匹配下一个字符；如果失配，即S[i + j] != T[j]，需要让i++,并且j= 0，即每次匹配失败的情况下，模式串T相对于原始串S向右移动了一位。

而KMP算法中，如果当前字符匹配成功，即S[i]==T[j]，令i++，j++，继续匹配下一个字符；如果匹配失败，即S[i] != T[j]，需要保持i不变，并且让j = next[j]，这里next[j] <=j -1，即模式串T相对于原始串S向右移动了至少1位(移动的实际位数j - next[j] >=1), 同时移动之后，i之前的部分（即S[i-j+1 ~ i-1]），和j=next[j]之前的部分（即T[0 ~ j-2]）仍然相等。

字符串匹配算法详解(下)字符串匹配算法详解(上)介绍了BF算法和KMP算法，这一篇接着来介绍Horspool算法和BM算法。

其中Horspool算法相当于是BM算法的特例，或者说是简化版的BM算法。

算法三：Horspool算法Horspool是后缀搜索，有点创新啊，大家都从左往右匹配，它反着来。

也就是搜索已读入文本中是否含有模式串的后缀；如果有，是多长，显然，当后缀长度等于模式串的长度时，我们就找到了一个匹配。

Horspool算法思想：模式串从右向左进行匹配。

对于每个文本搜索窗口，将窗口内的最后一个字符（C）与模式串的最后一个字符进行比较。

如果相等，则继续从后向前验证其他字符，直到完全相等或者某个字符不匹配。

然后，无论匹配与否，都将根据在模式串的下一个出现位置将窗口向右移动。

模式串与文本串口匹配时，模式串的整体挪动，是从左往右，但是，每次挪动后，从模式串的最后一个字符从右往左进行匹配。

下面我们来看一个实例：加上匹配串和模式串如下：匹配串：abcbcsdLinac-codecbcac模式串：cbcac首先从右向左进行匹配，c与c匹配成功，接着第二个字符b与a，匹配失败（失配位置为3）。

于是，从模式串当前位置往左寻找匹配失败的那个字符，也即在模式串中寻找字符b上一次出现的位置(注意这里的“上一次”是指在模式串中从当前失配位置往左找到的第一个与失配位置相同的字符)；结果我们在模式串中找到了字符b，其位置为1，那么就将模式串整体往右挪动，把刚才找到的字符b与之前与匹配串中失配的字符b 对齐。

总共移动了多少位呢？移动了（3-1）位。

匹配串：abcbcsdLibac-codecbcac模式串：? cbcac模式串整体挪动到b处对齐后，再从右向左开始匹配，此时发现其第一个需要匹配的字符d与c就匹配失败（失配位置为4），尼玛，坑爹啊！那接下来怎么办？当然是跟上一步的方法一样，在模式串中去找失配的那个字符d，如果在模式串中找到了d，将模式串平移，使其d字符与匹配串的d对齐。

BF算法与KMP算法BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将⽬标串S的第⼀个字符与模式串T的第⼀个字符进⾏匹配，若相等，则继续⽐较S的第⼆个字符和 T的第⼆个字符；若不相等，则⽐较S的第⼆个字符和T的第⼀个字符，依次⽐较下去，直到得出最后的匹配结果。

BF算法实现：1int BF(char S[],char T[],int pos)2 {//c从第pos位开始搜索匹配3int i=pos,j=0;4while(S[i+j]!='\0'&&T[j]!='\0')5 {6if(S[i+j]==T[j])7 j++;8else9 {10 i++;11 j=0;12 }13 }14if(T[j]=='\0')15return i+1;16else17return -1;18 }BF算法⽐较直接，是⼀种蛮⼒算法，该算法最坏情况下要进⾏M*(N-M+1)次⽐较，为O(M*N)，下⾯来看⼀个效率⾮常⾼的字符串匹配算KMP算法完成的任务是：给定两个字符串S和T，长度分别为n和m，判断f是否在S中出现，如果出现则返回出现的位置。

常规⽅法是遍历KMP算法思想:实例1优化的地⽅：如果我们知道模式中a和后⾯的是不相等的，那么第⼀次⽐较后，发现后⾯的的4个字符均对应相等，可见a下次匹配的位置实例2由于abc 与后⾯的abc相等，可以直接得到红⾊的部分。

⽽且根据前⼀次⽐较的结果，abc就不需要⽐较了，现在只需从f-a处开始⽐较即可。

说明主串对应位置i的回溯是不必要的。

要变化的是模式串中j的位置（j不⼀定是从1开始的，⽐如第⼆个例⼦）j的变化取决于模式串的前后缀的相似度，例2中abc和abc（靠近x的），前缀为abc，j=4开始执⾏。

下⾯我们来看看Next()数组：定义：（1）next[0]= -1 意义：任何串的第⼀个字符的模式值规定为-1。

天津市大学软件学院实验报告课程名称：串匹配算法实验姓名：***学号：**********班级：业务1114串匹配问题一、实验题目：给定一个主串，在该主串中查找并定位任意给定字符串。

二、实验目的：(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计算法的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。

三、实验分析：串匹配问题的BF算法1 在串S中和串T中设比较的下标i=1和j=1;2 循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完2.1 k=i2.2 如果S[i]=T[j],则比较S和T的下一字符,否则2.2 将i和j回溯(i=k+1; j=1)3 如果T中所有字符均比较完,则匹配成功,返回k否则匹配失败,返回0时间复杂度：设匹配成功发生在si处，则在i-1趟不成功的匹配中比较了（i-1）m次，第i趟成功匹配共比较了m次，所以总共比较了i m次，因此平均比较次数是：pi(i m)=(i m)=一般情况下，m<<n,因此最坏情况下时间复杂度是Ο(n m)。

串匹配问题的KMP算法实现过程：在串S和串T中高比较的起始下标i和j；循环直到S中所剩字符小于T的长度或T的所有字符均比较完（如果S[i]=T[j],则继续比较S和T的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0,则将i和j分别+1，准备下趟比较，至于其中的next在此不作详细讲解）；如果T中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。

时间复杂度：Ο(n m)，当m<<n时，KMP算法的时间复杂性是Ο(n)。

四、实验所用语言和运行环境C++，运行环境Microsoft Visual C++ 6.0五、实验过程的原始记录BF算法程序代码#include<iostream.h>#include<string>void main(){cout<<"请输入主串并且以0和回车结束"<<endl;char s[100];char t[100];for(int m=0;m<100;m++){cin>>s[m];if(s[m]=='0'){s[m]='\0';break;}}cout<<"您输入的主串为：";for(int o=0;o<strlen(s);++o){cout<<s[o];}cout<<endl;cout<<"主串长度：";cout<<strlen(s);cout<<endl<<endl;cout<<"请输入子串并且以0和回车结束"<<endl;for(int n=0;n<100;n++){cin>>t[n];if(t[n]=='0'){t[n]='\0';break;}}cout<<"您输入的子串为：";for(int a=0;a<strlen(t);++a){cout<<t[a];}cout<<endl;cout<<"子串长度：";cout<<strlen(t);cout<<endl;cout<<endl<<"++++++++BF算法++++++++"<<endl;int i,j,k,y=0;for(i=0;i<strlen(s)-strlen(t)+1;){k=i;for(j=0;j<strlen(t);)if(s[i]==t[j]){if(j==strlen(t)-1){cout<<"找到了相同的字串：";cout<<"位置在主串的第"<<i-j+1<<"的位置上";cout<<endl;y=1;break;}++i;++j;}else{j=0;break;}}i=k+1;if(y==1)break;}if(i==strlen(s)-strlen(t)+1&&j!=strlen(t)-1){cout<<"没有找到可以匹配的子串"<<endl;}}程序执行结果：查找到了子串没有查找到子串程序代码#include<iostream.h>#include<string>//前缀函数值,用于KMP算法int GETNEXT(char t[],int b){int NEXT[10];NEXT[0]=-1;int j,k;j=0;k=-1;while(j<strlen(t)){if ((k==-1)||(t[j]==t[k])){j++;k++;NEXT[j]=k;}else k=NEXT[k];}b=NEXT[b];return b;}int KMP(char s[],char t[]){int a=0;int b=0;int m,n;m=strlen(s); //主串长度n=strlen(t); //子串长度cout<<endl<<"+++++++++KMP算法++++++++++++"<<endl;while(a<=m-n){while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){cout<<"找到了相应的子串位置在主串："<<a-b+1<<endl;return 0;}b=GETNEXT(t,b);a=a-b;if(b==-1) b++;}cout<<"没有找到匹配的子串！"<<endl;return 0;}void main(){cout<<"请输入主串并且以0和回车结束"<<endl;char s[100];char t[100];for(int m=0;m<100;m++){cin>>s[m];if(s[m]=='0'){s[m]='\0';break;}}cout<<"您输入的主串为：";for(int o=0;o<strlen(s);++o){cout<<s[o];}cout<<endl;cout<<"主串长度：";cout<<strlen(s);cout<<endl<<endl;cout<<"请输入子串并且以0和回车结束"<<endl;for(int n=0;n<100;n++){cin>>t[n];if(t[n]=='0'){t[n]='\0';break;}}cout<<"您输入的子串为：";for(int a=0;a<strlen(t);++a){cout<<t[a];}cout<<endl;cout<<"子串长度：";cout<<strlen(t);cout<<endl;KMP(s,t);}程序执行结果：查找到子串没有查到子串。

字符串精确匹配算法改进的探讨如何改进字符串匹配算法，提高查询速度，是目前研究的重要领域之一，本文在对BF算法、KMP算法、BM算法、BMH算法、RK算法和SUNDAY算法等几种常见算法分析的基础上，提出改进的意见。

标签：精确匹配；KMP算法；模糊匹配一、引言字符串精确匹配在计算机领域有着广泛的应用, 它可用于数据处理、数据压缩、文本编辑、信息检索等多方面。

如何改进字符串匹配算法，提高查询速度，是目前研究的重要领域之一。

所谓精确字符串匹配问题，是在文本S中找到所有与查询P 精确匹配的子串。

字符串精确匹配要求匹配严格准确，其实现算法主要有BF算法、KMP算法、BM算法、BMH算法、RK算法和SUNDAY算法等。

本文在对这几种常见算法分析的基础上，提出改进的意见。

二、常见算法分析1．BF算法BF(Brute Force)算法是效率最低的算法。

其核心思想是：T是文本串，P是模式串。

首先S[1]和P[1]比较，若相等，则再比较S[2]和P[2]，一直到P[M]为止；若S[1]和P[1]不等，则P 向右移动一个字符的位置，再依次进行比较。

如果存在t，1≤t≤N，且S[t+1..t+M]= P[1..M],则匹配成功；否则失败。

该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。

2．KMP 算法KMP(Knuth-Morris-Pratt)算法是D.E.Knuth、J.H.Morris和V.R.Pratt 3 人于1977 年提出来的。

其核心思想是：在匹配失败时，正文不需要回溯，而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离，继续进行比较。

这里要强调的是，模式串不一定向右移动一个字符的位置，右移也不一定必须从模式串起点处重新试匹配，即模式串一次可以右移多个字符的位置，右移后可以从模式串起点后的某处开始试匹配。

KMP算法的时间复杂度是O(m+n)，最坏情况下时间复杂度为O（m*n）。

bf算法与kmp算法执行流程英文回答：The Boyer-Moore (BM) algorithm and the Knuth-Morris-Pratt (KMP) algorithm are two popular string matching algorithms used to find occurrences of a pattern within a larger text. While both algorithms have the same goal, they differ in their approach and execution flow.The Boyer-Moore algorithm is a heuristic algorithm that uses two main techniques: the bad character rule and the good suffix rule. The bad character rule allows the algorithm to skip comparisons by shifting the pattern to align with the last occurrence of a mismatched character in the text. The good suffix rule, on the other hand, allows the algorithm to shift the pattern based on the longest suffix of the pattern that matches a prefix of itself.The execution flow of the Boyer-Moore algorithm can be summarized as follows:1. Preprocessing: The algorithm starts by preprocessing the pattern to create two lookup tables: the bad character table and the good suffix table.2. Searching: The algorithm then starts searching for the pattern in the text by aligning the pattern with the current position in the text and comparing characters from right to left.3. Mismatch: If a mismatch occurs, the algorithm uses the bad character rule to determine the amount of shift needed.4. Shift: The algorithm shifts the pattern to the right based on the maximum of the bad character rule and the good suffix rule.5. Repeat: Steps 3 and 4 are repeated until either a match is found or the end of the text is reached.The Knuth-Morris-Pratt algorithm, on the other hand, isa linear time algorithm that uses a failure function to avoid unnecessary comparisons. The failure function is computed based on the pattern itself and allows the algorithm to determine the maximum amount of shift when a mismatch occurs.The execution flow of the Knuth-Morris-Pratt algorithm can be summarized as follows:1. Preprocessing: The algorithm starts by preprocessing the pattern to create the failure function.2. Searching: The algorithm then starts searching for the pattern in the text by aligning the pattern with the current position in the text and comparing characters from left to right.3. Mismatch: If a mismatch occurs, the algorithm uses the failure function to determine the amount of shift needed.4. Shift: The algorithm shifts the pattern to the rightbased on the value of the failure function.5. Repeat: Steps 3 and 4 are repeated until either a match is found or the end of the text is reached.中文回答：Boyer-Moore（BM）算法和Knuth-Morris-Pratt（KMP）算法是两种常用的字符串匹配算法，用于在较大的文本中查找模式的出现。

现代网络搜索引擎一般使用基于字符串匹配的搜索方式，使用的软件核心之一是字符串模式匹配算法。

网络特别是Internet 的信息量极大，在相同的信息采集方式下网络搜索的时间主要取决于所使用的串匹配算法的效率。

改善串匹配算法的特性或者时间复杂度，将有效提高网络搜索引擎的性能。

所以算法的提出和后续改进的算法称为研究的重点。

模式匹配主要有BF 算法，KMP 算法，BM 算法及其改进算法，尤其是BM 算法，在实际应用中非常著名，在此我们将对这几种算法做简单分析，分析前，我们做如下假定：文本：]1..0[-n text n 为文本长度模式：]1..0[-m pat m 为模式长度2.1 BF 算法BF （Brute Force ）算法又称为蛮力匹配算法[2]，这是一种效率很低的算法，其算法主要思想是模式的第一个字符与文本的第一个字符进行比较，如果相同，就继续比较后面的字符，否则，文本的起始位置加1，即模式右移一个位置，再进行比较，如果模式与文本中一段连续字符串都相同，则匹配成功，返回当时文本的起始比较位置，否则匹配不成功，实现过程：在串text 和串pat 中比较的起始下标i 和j ；循环直到text 中所剩字符小于pat 的长度或pat 的所有字符均比较完（如果text[i]=pat[j]，则继续比较text 和pat 的下一个字符；否则将i 和j 回溯，准备下趟比较）；如果pat 中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。

BF 算法如下：Algorithm BFk=0;j=0;while ((j<=m)&&(k<=n-m)){ if (pat[j]==text[k]){ k++;j++;}Else{k=k-j+1;j=0;}}if (j= =m) Match found at text[k-m]else No match found例子1：文本：astringsearchingexamplelienvolingrelatively模式串：relative1. astringsearchingexamplelienvolingrelativelyrelative2. astringsearchingexamplelienvolingrelativelyrelative3. astringsearchingexamplelienvolingrelativelyrelative4. astringsearchingexamplelienvolingrelativelyrelative：32. astringsearchingexamplelienvolingrelativelyrelative该算法简单，但是效率较低。