一.简单的字符串匹配
我们经常需要在某一串字符中查找是否存在给定的子串，我们将给定的子串叫做模式，查找子串的问题叫做模式匹配。
进行字符串的模式匹配，最简单的方法就是依次将子串与给定的字符串依次进行比较。算法如下：
int patFind(const char* str, const char* pat){
int pos1,pos2;
bool isfind;
int i=0;
pos1=i;
pos2=0;
while(str[pos1]!='\0'&&pat[pos2]!='\0'){
if(str[pos1++]!=pat[pos2++]){
pos1=++i;
pos2=0;
}
}
if(pat[pos2]=='\0'){
return i;
}
return -1;
}
简单的匹配算法存在回溯现象，复杂度为O(m*n)
二.KMP算法的思想
在匹配的时候经常会碰到回溯，而根据对Pattern的先验计算，能避免回溯，提高匹配效率，KMP算法就是通过对Pattern进行先验计算来避免回溯的算法。
如p0...pi与ts...ts+i匹配，pi+1与ts+i+1不等，这时按照简单的匹配算法，将继续第s+1趟比较比较p0...pi-1...pm与ts+1...ts+i...ts+1+m,如果这两者匹配，那么有
p0...pi-1=ts+1...ts+i=p1...pi
这时，如果已知两者不等，那么就不用做第s+1趟比较了。同理，如果已知p0...pi-2不等于p2...pi那么就不用做第s+2趟比较。
依此类推，直到找到最大的k，使得p0...pk=pi-k...pi，这时可以直接做第s+i-k趟比较，并因为已知p0...pk=pi-k...pi=ts+i-k...ts+i了，直接比较pk+1和ts+i+1即可。
这时我们可以定义一个失效函数f(i)，比较至pi，使得pi匹配，pi+1不匹配时，其值等于使得p0...pk=pi-k...pi且小于i的最大k值，如果找不到则值为-1.
https://www.doczj.com/doc/559402858.html,
对于模式pat=abaabcaba，
f(0)为-1
因为p0!=p1, f(1)为-1
因为p0=p2,f(2)为0
因为p0=p3,f(3)为0
因为p0p1=p3p4,f(4)为1
f(5)为-1
f(6)为0
f(7)为1
f(8)为2
如果第s趟比较在第i位失配，则下一趟直接比较pf(i-1)+1和ts+i
三.失效函数的计算
已知f(j-1)=k,则有p0...pk=pj-1-k...pj-1,这时如果pk+1=pj,则f(j)=k+1,如果不等，则继续找f(k),因为p0...pf(k)=pj-1-f(k)...pj-1,这时如果pf(k)+1=pj,则f(j)=f(k)+1,依此类推。我们可以得到下面的方法来计算失效函数。
void failFunc(const char* pat, int* fail){ fail[0]=-1;
int len=strlen(pat);
int k;
for(int j=1;j k=fail[j-1]; while(k>=0&&pat[k+1]!=pat[j]){ k=fail[k]; } if(pat[k+1]==pat[j]){ fail[j]=k+1; } else{ fail[j]=-1; } cout< } } https://www.doczj.com/doc/559402858.html, 四.KMP模式匹配算法的实现 int kmpFind(const char* str, const char* pat){ int pos1=0,pos2=0; int patlen=strlen(pat); int* fail=new int[patlen]; failFunc(pat,fail); while(str[pos1]!='\0'&&pat[pos2]!='\0'){ if(str[pos1]==pat[pos2]){ pos1++; pos2++; } else if(pos2==0){ pos1++; } else{ pos2=fail[pos2-1]+1; } } if(pat[pos2]=='\0'){ return pos1-patlen; } return-1; } 虽然计算失效函数需要浪费一定的时间和空间，可是从代码我们可以看到KMP没有任何的回溯，时间复杂度仅为(m+n),当模式比较长时KMP算法比起简单的模式匹配有显著的优势。 运行结果： int_tmain(int argc, _TCHAR* argv[]) { char str[] = "ababaabaabaabcabaaaabbcccc"; char pat[] = "abaabcaba"; cout< cout< return0; } 各种排序算法的实现 一.基本概念 1.稳定排序与不稳定排序: 对于A,B两个键值相等的对象，且在排序前，A在B之前，如果排序后A肯定还在B之前，则为稳定排序，如果B可能在A之前，为不稳定排序。 2.内排序和外排序： 内排序是指在排序期间数据对象全部存放在内存的排序 外排序是指在排序期间数据对象太多，不能同时存放在内存，必须依照排序过程的要求，不断在内外存之间移动的排序。 二.各种排序算法的实现 1.插入排序 基本思想：插入第i个对象时前i-1个对象已经排好了，将第i个对象插入前i-1个对象的合适地方，使得前i个对象有序。是稳定排序，比较次数和移动次数复杂度都为O(n^2) void insertSort(int* disorder, int size){ int temp=0,i=0; for(int j=1;j temp=disorder[j]; for(i=j;i>0;i--){ if(temp disorder[i] = disorder[i-1]; } else{ break; } } disorder[i]=temp; } } 2.希尔排序 基本思想：将数列以gap作为间隔分成子序列，分别对子序列进行插入排序，再逐步缩小间隔进行插入排序。shell提出gap取floor(n/2),gap=floor(gap/2).这是一种不稳定的排序。 void shellSort(int* disorder, int size){ int gap=size/2; int temp=0,i=0; while(gap>0){ for(int g=0;g for(int j=g+gap;j temp=disorder[j]; for(i=j;i>gap-1;){ if(temp disorder[i] = disorder[i-gap]; i=i-gap; } else{ break; } } disorder[i]=temp; j=j+gap; } } gap=gap/2; } } 3.起泡排序 基本思想：依次比较key(n)和key(n-1),直到key(2)和key(1)，这样会使最小的对象被起泡到第一个，依次进行起泡，完成排序。是稳定排序，比较次数和移动次数复杂度都为O (n^2) void bubbleSort(int* disorder, int size){ int temp=0,modified=0; for(int j=1;j modified=0; for(int i=size-1;i>j-1;i--){ if(disorder[i] temp = disorder[i]; disorder[i] = disorder[i-1]; disorder[i-1]=temp; modified++; } } if(modified==0){ break; } } } 4.快速排序 基本思想：任取一个对象作为基准，按照关键码的大小，将排序队列分为左右两个子序列，小于该对象的都放在左序列，大于该对象的都放在右序列，然后分别对两个子序列重复上述方法，直到所有对象有序排列。是不稳定排序，比较次数和移动次数复杂度都为O(n*log n) void quickSort1(int* disorder, int start, int end){ if(start>=end){ return; } int middle=disorder[start]; int temp=0; int pivotpos=start+1,i=start+1; for(;i<=end;i++){ if(disorder[i] if(i!=pivotpos){ temp=disorder[i]; disorder[i]=disorder[pivotpos]; disorder[pivotpos]=temp; } pivotpos++; } } disorder[start]=disorder[pivotpos-1]; disorder[pivotpos-1]=middle; quickSort1(disorder,start,pivotpos-2); quickSort1(disorder,pivotpos,end); } void quickSort(int* disorder, int size){ quickSort1(disorder,0,size-1); } 5.选择排序 基本思想：每一趟在后面n-i个待排序对象中选出关键码最小的对象，作为有序对象集的第i个对象。不稳定的排序，比较次数为O(n^2),移动次数为O(n) void selectSort(int* disorder, int size){ int temp=0,small; for(int j=0;j temp=disorder[size-1]; small=size-1; for(int i=size-2;i>j-1;i--){ if(disorder[i] temp=disorder[i]; small=i; } } disorder[small]=disorder[j]; disorder[j]=temp; } } 6.锦标赛排序 基本思想：利用胜者树来进行选择排序。稳定的排序，比较次数为O(n*logn). 锦标赛排序虽然节省时间，但是对空间有较大浪费，不推荐 7.堆排序 基本思想：利用最大堆，将得到的最大元素依次调整到最后。不稳定的排序，时间复杂度为O(n*logn). void filterDown(int* disorder, int pos, int size){ int temppos=pos,temp=0; while(temppos if(2*temppos+2 if(disorder[2*temppos+1]>disorder[2*temppos+2]){ if(disorder[temppos] temp=disorder[temppos]; disorder[temppos]=disorder[2*temppos+1]; disorder[2*temppos+1]=temp; temppos=2*temppos+1; } else{ break; } } else{ if(disorder[temppos] temp=disorder[temppos]; disorder[temppos]=disorder[2*temppos+2]; disorder[2*temppos+2]=temp; temppos=2*temppos+2; } else{ break; } } } else if(disorder[temppos] temp=disorder[temppos]; disorder[temppos]=disorder[2*temppos+1]; disorder[2*temppos+1]=temp; temppos=2*temppos+1; } else{ break; } } } void heapSort(int* disorder, int size){ int bottomRowSize=2; while(bottomRowSize bottomRowSize*=2; } int temp=0,i=0; for(int j=size/2-1;j>=0;j--){ filterDown(disorder, j, size); } for(int j=size-1;j>0;j--){ temp=disorder[0]; disorder[0]=disorder[j]; disorder[j]=temp; filterDown(disorder,0,j-1); } } 8.归并排序 基本思想：先两两排序，再逐步进行归并。稳定的排序，时间复杂度为O(n*logn). void merge(int* source,int*dest, int gap, int size){ int pos1,pos2,end1,end2,destpos=0; for(int i=0;i pos1=i; end1=i+gap>size?size:i+gap; pos2=i+gap; end2=i+2*gap>size?size:i+2*gap; while(pos1 if(source[pos1] dest[destpos]=source[pos1]; pos1++; } else{ dest[destpos]=source[pos2]; pos2++; } destpos++; } while(pos1 dest[destpos++]=source[pos1++]; } while(pos2 dest[destpos++]=source[pos2++]; } } } void mergeSort(int* disorder, int size){ int gap=1; int* temparr= new int[size]; while(gap merge(disorder, temparr,gap,size); gap*=2; merge(temparr,disorder,gap,size); gap*=2; } delete[] temparr; } 9.基数排序 基本思想：利用分配和收集的方法进行排序，比如已知数字不超过100，可以按照十位数先进行分配，再分别进行排序后将数字收集起来。 三.排序结果的检验 对于排序算法，可以用下列的方法来生成一系列的随机数进行排序，并用isSorted函数来检验是否正确的排序了。 bool isSorted(int* disorder, int size){ for(int i=0;i if(disorder[i]>disorder[i+1]) return false; } return true; } int_tmain(int argc, _TCHAR* argv[]) { const int size=200; const int maxnum = 10000; int* disorder=new int[size]; srand((unsigned) time(NULL)); for(int i=0;i disorder[i]=rand()%maxnum; } mergeSort(disorder,size); for(int i=0;i cout< } cout< return0; } 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊： KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS); int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n 实验7、字符串查找 目的 掌握字符串模式匹配的经典算法。 问题描述 分别用简单方法和KMP方法实现index在文本串中查找指定字符串的功能。 步骤 1.定义字符串类型 2.实现简单的index操作，从文本串中查找指定字符串。 3.实现KMP方法的index操作，从文本串中查找指定字符串。 4.[选]建立一个文本文件，读入每一行来测试自己完成的练习，观察并理解程序的各 个处理。 设备和环境 PC计算机、Windows操作系统、C/C++开发环境 结论 能够理解和掌握字符串模式匹配的典型算法。 思考题 1.对KMP算法分别用手工和程序对某个模式串输出next和nextval。 朴素算法： #include #define ERROR -2 #define MAXLEN 100//字符串的最大长度 char S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10];//串S和串T int S0,T0; //S0：串S的长度 T0：串T的长度 int pos; //pos的起始位置 void Init(char *S,int &S0)//读入字符串 { int len,i; New_Input: scanf("%s",st);//读入字符串 len=strlen(st); if (len>MAXLEN)//如果字符串的长度大于规定的字符串最大长度 { printf("This String is too long,Please Input a new one.nn"); goto New_Input;//重新读入字符串 字符串匹配算法的研究及其程序实现 计算机学院计算机科学与技术专业2007级指导教师：滕云 摘要：在字符串匹配算法之中，最古老和最著名的是由D. E. Knuth, J. h. Morris, V. R. Pratt 在1997年共同提出的KMP算法。直至今日，人们对字符串匹配问题还在进行着大量的研究，以寻求更简单，或者平均时间复杂度更优的算法;学者们在不同的研究方向上，设计出了很多有效的匹配算法。在现实生活中，串匹配技术的应用十分广泛，其主要领域包括：入侵检测，病毒检测，信息检索，信息过滤，计算生物学，金融检测等等。在许多应用系统中，串匹配所占的时间比重相当大，因此，串匹配算法的速度很大程度上影响着整个系统的性能。该论文重点分析了KMP算法的实现原理和C语言实现，并在此基础上提出了改进的KMP算法，使得该算法更方便实用。 关键词：KMP算法；时间复杂度；串匹配；改进；方便使用； String matching algorithm and Implementation of the Program College of Computer Sciences, Computer Science and Technology Professional grade 2007, Instructor YunTeng Abstractor:Among the string matching algorithm,the oldest and most famous is KMP algorithm co-sponsored by D.E Knuth, J. h. Morris, VR Pratt in 1997. As of today, a lot of research to String matching are still in progress, to seek a more simply or better average time complexity of the algorithm. In different research direction, scholars have designed a lot of valid matching.In real life, the string matching technique is widely used，The main areas include: intrusion detection, virus detection, information retrieval, information filtering, computational biology, financial inspection and so on.In many applications，a large percentage of the time was placed by the string matching, so the string matching algorithms significantly affect the speed performance of the whole system.The paper analyzes the implementation of the KMP algorithm theory and through the C language to achieve it.And we puts forward a modified KMP algorithm in order to makes the algorithm more convenient and practical. Key words:KMP algorithm; Time complexity; String matching; Improved; Easy to use; 实验题目：字符串的模式匹配 一、实验描述 用BF算法实现字符串的模式匹配 二、实验目的和任务 从主串的第pos位置字符开始和模式子串字符比较，如果相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式子串的字符比较。直到找到匹配字符串或者是主串结尾。 三、概要设计 BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。 四、运行与测试 #include { char *szSource = "ababcababa"; char *szSub = "ababa"; int index =BFMatch(szSource, szSub); printf("目标串包含匹配串的起始位置：%d",index); } 五、运行结果 六、实验心得 通过这次课程设计，让我了解了字符串的定位操作即字符串模式匹配的基本概念和算法,探讨了字符串模式匹配操作的最基本的BF匹配算法。虽然看起来很简单的程序，做起来却遇到了不少问题，编程中出行了一些小错误，多次查改之后再进行修改，所以我觉得在以后的学习中，我会更加注重实践，注重多练，多积累。 课程设计报告题目：字符串匹配算法实测分析 课程名称：数据结构 专业班级：计科XX 学号：UXXXXX XX 姓名：FSH 指导教师：xxx 报告日期：2015.9.13 计算机科学与技术学院 数据结构课程组 2015年5月 题目字符串匹配算法实测分析 ?设计目的：掌握线性结构中的字符串的物理存储结构与基本算法，通过查询阅读文献资料，拓广知识面以及培养学生科研能力。 ?设计内容：结合教材上的字符串匹配算法，查询文献资料检索4种以上的有关精确匹配算法，掌握算法原理并实现。 ?设计要求： （1）查阅相关的文献资料，特别是留意年近些年发表的文献资料； （2）要求对各种算法进行理论分析，同时也对实测结果进行统计分析。测试数据要求有一定规模，比如一本书或不少于50篇的中英文文献。 （3）要求界面整洁、美观，操作方便； 报告内容： （一）, 运行界面，及运行结果截图 （二）,各算法的具体分析，包括起源，基本思路，实例分析，具体实现，和本算法代码。 （三），总程序源代码。 （四），课程设计心得 （一）, 运行界面，运行结果说明： 运行代码显示界面： 对于S串可以手动输入字符串检索，也可以选择在计算机里建好的TXT文件，按任意键退出。 按2确认，键入一本书的TXT文件，运行如下 输入待搜索子串“史记”得到运行结果，各算法均返回子串在母串出现的位置 执行算法得运行结果，返回子串在母串所有出现位置。 结果显示运行时间用以统计时间效率： 另一段检索结果的时间截图结果显示如下： （二）,各算法的具体分析 一．穷举算法（Brute force）算法： . 1.算法起源： 此算法思路简单，容易想到，没有确定的提出者‘ 《KMP字符串模式匹配算法》教学课例 程玉胜 安庆师范学院计算机与信息学院 KMP字符串模式匹配是数据结构课程中一个重要的知识点，也是一个难点（学过KMP 算法的同学100％认为:KMP是数据结构课程中最难的部分）。为了消除他们对KMP算法学习的恐惧心理，激发他们的学习兴趣，调动其积极性，显得尤为重要。 基于以上，我们根据学生的认知特点和接受水平，对教材内容进行了重新构建，并按照数据结构中?时间复杂度?概念，增加了不同模式匹配算法的运行时间，动态逼真的显示了算法的?时间?性能，获得了较好的教学效果。 一、教学目标 知识目标：让学生了解KMP算法应用的普遍性。如：在目前众多的文字处理软件中得到广泛应用，如Microsoft Word中的?查找?或?替换?操作。而这种操作实现的机制，同学们特别是计算机专业的学生很少去想过。 能力目标：要求学生体验一个完整的抽象数据类型（ADT）的实现方法和过程，并学会判断、计算算法优劣的方法。 价值目标：消除恐怖的学习心态，让学生感悟数据结构算法实际应用价值，从而激发学习的兴趣，形成积极主动式学习的态度。 二、教材分析 使用教材是清华大学严蔚敏教授并由清华大学出版社出版的《数据结构（C语言版）》，该教材难度较大，其实验方法特别是ADT方法在教材中介绍较少，而且KMP算法更是从理论分析的角度介绍了匹配算法和next的计算，自学难度很大；虽然该节知识点属于?**（表示难度较大，可以不讲）?，但是其又是考研的一个热点，所以我们又不得不讲。 三、教学重点、难点 教学重点：KMP算法中的next和改进的nextval计算 教学难点：KMP算法中如何计算next值 四、教具准备 卡片：多个字符串，字符串指针 强力磁吸：6个 五、互动式教学过程 字符串匹配算法（一）简介收藏 注：本文大致翻译自EXACT STRING MATCHING ALGORITHMS，去掉一些废话，增加一些解释。 文本信息可以说是迄今为止最主要的一种信息交换手段，而作为文本处理中的一个重要领域——字符串匹配，就是我们今天要说的话题。（原文还特意提及文本数据数量每18个月翻一番，以此论证算法必须要是高效的。不过我注意到摩尔定律也是18个月翻番，这正说明数据的增长是紧紧跟随处理速度的，因此越是使用高效的算法，将来待处理的数据就会越多。这也提示屏幕前的各位，代码不要写得太快了……） 字符串匹配指的是从文本中找出给定字符串（称为模式）的一个或所有出现的位置。本文的算法一律输出全部的匹配位置。模式串在代码中用x[m]来表示，文本用y[n]来，而所有字符串都构造自一个有限集的字母表Σ，其大小为σ。 根据先给出模式还是先给出文本，字符串匹配分为两类方法： ?第一类方法基于自动机或者字符串的组合特点，其实现上，通常是对模式进行预处理； ?第二类方法对文本建立索引，这也是现在搜索引擎采用的方法。 本文仅讨论第一类方法。 文中的匹配算法都是基于这样一种方式来进行的：设想一个长度为m的窗口，首先窗口的左端和文本的左端对齐，把窗口中的字符与模式字符进行比较，这称为一趟比较，当这一趟比较完全匹配或者出现失配时，将窗口向右移动。重复这个过程，直到窗口的右端到达了文本的右端。这种方法我们通常叫sliding window。 对于穷举法来说，找到所有匹配位置需要的时间为O(mn)，基于对穷举法改进的结果，我们按照每一趟比较时的比较顺序，把这些算法分为以下四种： 1.从左到右：最自然的方式，也是我们的阅读顺序 2.从右到左：通常在实践中能产生最好的算法 3.特殊顺序：可以达到理论上的极限 4.任意顺序：这些算法跟比较顺序没关系（例如：穷举法） 一些主要算法的简单介绍如下： 从左到右 采用哈希，可以很容易在大部分情况下避免二次比较，通过合理的假设，这种算法是线性时间复杂度的。它最先由Harrison提出，而后由Karp和Rabin全面分析，称为KR算法。 在假设模式长度不大于机器字长时，Shift-Or算法是很高效的匹配算法，同时它可以很容易扩展到模糊匹配上。MP是第一个线性时间算法，随后被改进为KMP，它的匹配方式很类似于自动机的识别过程，文本的每个字符与模式的每个字符比较不会超过logΦ(m+1)，这里Φ是黄金分隔比1.618，而随后发现的类似算法——Simon算法，使得文本的每个字符比较不超过1+log2m，这三种算法在最坏情况下都只要2n-1次比较。（抱歉限于我的水平这一段既没看懂也没能查证，大家就看个意思吧） 基于确定性有限自动机的算法对文本字符刚好只用n次访问，但是它需要额外的O(mσ)的空间。 一种叫Forward Dawg Matching的算法同样也只用n次访问，它使用了模式的后缀自动机。 Apostolico-Crochemore算法是一种简单算法，最坏情况下也只需要3n/2次比较。 还有一种不那么幼稚（Not So Naive）的算法，最坏情况下是n平方，但是预处理过程的时间和空间均为常数，而且平均情况下的性能非常接近线性。 从右到左 BM算法被认为是通常应用中最有效率的算法了，它或者它的简化版本常用于文本编辑器中的搜索和替换功能，对于非周期性的模式而言，3n是这种算法的比较次数上界了，不过对于周期性模式，它最坏情况下需要n的二次方。字符串的模式匹配算法
字符串匹配算法总结
KMP字符串模式匹配算法解释
C语言字符串模式匹配
字符串模式匹配
字符串匹配算法的研究_本科论文
字符串的模式匹配实验报告
字符串匹配算法报告
《KMP 字符串模式匹配算法》教学课例
C语言 字符串匹配算法
相关主题
文本预览