数据结构- 串的模式匹配算法：BF和 KMP算法

串的两种模式匹配算法 模式匹配(模范匹配)：⼦串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。

模式匹配成功是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。

以下介绍两种常见的模式匹配算法：1. Brute-Force模式匹配算法暴风算法，⼜称暴⼒算法。

算法的核⼼思想如下： 设S为⽬标串，T为模式串，且不妨设： S=“s0s1s2…sn-1” ， T=“t0t1t2 …tm-1” 串的匹配实际上是对合法的位置0≦i≦n-m依次将⽬标串中的⼦串s[i…i+m-1]和模式串t[0…m-1]进⾏⽐较：若s[i…i+m-1]=t[0…m-1]：则称从位置i开始的匹配成功，亦称模式t在⽬标s中出现；若s[i…i+m-1]≠t[0…m-1]：从i开始的匹配失败。

位置i称为位移，当s[i…i+m-1]=t[0…m-1]时，i称为有效位移；当s[i…i+m-1] ≠t[0…m-1]时，i称为⽆效位移。

算法实现如下： （笔者偷懒，⽤C#实现，实际上C# String类型已经封装实现了该功能）1public static Int32 IndexOf(String parentStr, String childStr)2 {3 Int32 result = -1;4try5 {6if (parentStr.Length > 1 && childStr.Length > 1)7 {8 Int32 i = 0;9 Int32 j = 0;10while (i < parentStr.Length && j < childStr.Length)11 {12if (parentStr[i] == childStr[j])13 {14 i++;15 j++;16 }17else18 {19 i = i - j + 1;20 j = 0;21 }22 }23if (i < parentStr.Length)24 {25 result = i - j;26 }27 }28 }29catch (Exception)30 {31 result = -1;32 }33return result;34 } 该算法的时间复杂度为O(n*m) ，其中n 、m分别是主串和模式串的长度。

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。

数据结构—串的模式匹配数据结构—串的模式匹配1.介绍串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。

本文档将详细介绍串的模式匹配算法及其实现。

2.算法一：暴力匹配法暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。

具体步骤如下：1.从主串的第一个字符开始，逐个比较主串和模式串的字符。

2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。

3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。

3.算法二：KMP匹配算法KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。

具体步骤如下：1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。

4.算法三：Boyer-Moore匹配算法Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。

具体步骤如下：1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。

5.算法四：Rabin-Karp匹配算法Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。

具体步骤如下：1.计算模式串的哈希值。

2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。

字符串模式匹配算法系列（⼀）：BF算法算法背景：BF（Brute Force）算法，是⼀种在字符串匹配的算法中，⽐较符合⼈类⾃然思维⽅式的⽅法，即对源字符串和⽬标字符串逐个字符地进⾏⽐较，直到在源字符串中找到完全与⽬标字符串匹配的⼦字符串，或者遍历到最后发现找不到能匹配的⼦字符串。

算法思路很简单，但也很暴⼒。

算法原理：假设源字符串为“⾮常地⾮常地⾮常地喜欢你”，我们想从中寻找⽬标字符串“⾮常地⾮常地喜欢”，则BF算法的过程可以表述如下：第1轮：将源字符串和⽬标字符串对齐，并下标0开始逐个向后⽐较每个字符。

结果发现双⽅的第1个字符都是“⾮”、第2个字符都是“常”、……，但到了第7个字符时发现不⼀致：源字符串为“⾮”、⽬标字符串为“喜”，因此这⼀轮匹配不成功。

第2轮：将⽬标字符串整体向后移动1个字符的位置（即将⽬标字符串的第1个字符与源字符串的第2个字符对齐），并开始逐个向后⽐较每个字符，结果发现两个字符串的第1个字符就不⼀致，因此这⼀轮匹配也不成功。

第3轮：类似地，将⽬标字符串整体向后移动1个字符的位置（即将⽬标字符串的第1个字符与源字符串的第3个字符对齐），并开始逐个向后⽐较，结果发现两个字符串的第1个字符就不⼀致，因此这⼀轮匹配也不成功。

第4轮：这⼀轮终于发现，⽬标字符串的每个字符都能和源字符串对应起来，匹配成功！因此算法结束并根据需要返回相应的信息（⽐如返回这⼀轮源字符串遍历起始点的位置下标3）算法实现：BF算法的python实现如下：1#!/usr/bin/env python2#-*- coding: utf-8 -*-3import sys4import pdb56 reload(sys)7 sys.setdefaultencoding('utf-8')8910class BruteForce(object):11"""BF算法12成员变量:13 str_s: 源字符串14 str_t: ⽬标字符串15"""16def__init__(self, str_s, str_t):17 self.str_s = str_s18 self.str_t = str_t1920def run(self):21"""完全匹配则返回源字符串匹配成功的起始点的下标，否则返回-122"""23 base = 0 # 记录源字符串与⽬标字符串对齐的基准点24 len_s = len(self.str_s)25 len_t = len(self.str_t)2627while base + len_t <= len_s:28 step = 029while step < len_t:30if str_t[step] == self.str_s[base + step]:31# 当前字符相同，则继续⽐较下⼀个字符32 step += 133continue34# 当前字符不相同，则结束次轮⽐较，更新base基准位置，启动下⼀轮⽐较35 base += 136break37# 完全匹配成功，算法结论，返回匹配成功的基准点位置下标38if step == len_t:39return base40# 遍历了所有情况，最终匹配失败，返回-141return -1424344if__name__ == '__main__':45 str_s = u"⾮常地⾮常地⾮常地喜欢你"46 str_t = u"⾮常地⾮常地喜欢"47 model = BruteForce(str_s, str_t)48print model.run()复杂度分析：时间复杂度：假设源字符串长度为m，⽬标字符串长度为n，则：最好情况下是第⼀轮就成功匹配，则时间复杂度为O(n)；最坏情况下是遍历到最后才成功匹配，或者遍历到最后发现匹配不成功，则时间复杂度为O(n*(m-n+1))，⼀般实际使⽤时m >> n，所以可以认为趋近于O(m*n)；空间复杂度：由于不需要额外的存储空间，所以空间复杂度为O(1)算法评估：整个算法其实就循环执⾏如下两个步骤：⼀、从每⼀轮的基准点开始⽐较两个字符串；⼆、如发现不能完全匹配⽬标字符串，将⽬标字符串向后挪动⼀个字符的位置（即更新基准点）；如果想优化算法性能，那就简单分析⼀下：步骤⼀基本没有优化的空间：两个字符串⽐较就是需要从前向后逐个字符看是否匹配；步骤⼆可能有优化的空间：每轮发现不匹配时，⽬标字符串只能向后挪动⼀个字符的距离，所以会想到能否多往后挪动⼏个字符的距离？这样不就减少了步骤⼀⽐较的轮次数，从⽽加快速度了吗？这基本就是KMP算法的思路，下⼀篇会详细介绍。

天津市大学软件学院实验报告课程名称：串匹配算法实验姓名：***学号：**********班级：业务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);}程序执行结果：查找到子串没有查到子串。