文档介绍：字符串匹配指的是从文本中找出给定字符串(称为模式)的一个或所有出现的位置。本文的算法一律输出全部的匹配位置。模式串在代码中用x[m]来表示,文本用y[n]来,而所有字符串都构造自一个有限集的字母表Σ,其大小为σ。 根据先给出模式还是先给出文本,字符串匹配分为两类方法:·        第一类方法基于自动机或者字符串的组合特点,其实现上,通常是对模式进行预处理;·        第二类方法对文本建立索引,这也是现在搜索引擎采用的方法。本文仅讨论第一类方法。 文中的匹配算法都是基于这样一种方式来进行的:设想一个长度为m的窗口,首先窗口的左端和文本的左端对齐,把窗口中的字符与模式字符进行比较,这称为一趟比较,当这一趟比较完全匹配或者出现失配时,将窗口向右移动。重复这个过程,直到窗口的右端到达了文本的右端。这种方法我们通常叫slidingwindow。 对于穷举法来说,找到所有匹配位置需要的时间为O(mn),基于对穷举法改进的结果,我们按照每一趟比较时的比较顺序,把这些算法分为以下四种:1.   从左到右:最自然的方式,也是我们的阅读顺序2.   从右到左:通常在实践中能产生最好的算法3.   特殊顺序:可以达到理论上的极限4.   任意顺序:这些算法跟比较顺序没关系(例如:穷举法)一些主要算法的简单介绍如下: 从左到右采用哈希,可以很容易在大部分情况下避免二次比较,通过合理的假设,这种算法是线性时间复杂度的。它最先由Harrison提出,而后由Karp和Rabin全面分析,称为KR算法。在假设模式长度不大于机器字长时,Shift-Or算法是很高效的匹配算法,同时它可以很容易扩展到模糊匹配上。MP是第一个线性时间算法,随后被改进为KMP,它的匹配方式很类似于自动机的识别过程,文本的每个字符与模式的每个字符比较不会超过logΦ(m+1),,而随后发现的类似算法——Simon算法,使得文本的每个字符比较不超过1+log2m,这三种算法在最坏情况下都只要2n-1次比较。(抱歉限于我的水平这一段既没看懂也没能查证,大家就看个意思吧)基于确定性有限自动机的算法对文本字符刚好只用n次访问,但是它需要额外的O(mσ)的空间。一种叫ForwardDawgMatching的算法同样也只用n次访问,它使用了模式的后缀自动机。Apostolico-Crochemore算法是一种简单算法,最坏情况下也只需要3n/2次比较。还有一种不那么幼稚(NotSoNaive)的算法,最坏情况下是n平方,但是预处理过程的时间和空间均为常数,而且平均情况下的性能非常接近线性。 从右到左BM算法被认为是通常应用中最有效率的算法了,它或者它的简化版本常用于文本编辑器中的搜索和替换功能,对于非周期性的模式而言,3n是这种算法的比较次数上界了,不过对于周期性模式,它最坏情况下需要n的二次方。BM算法的一些变种避免了原算法的二次方问题,比较高效的有:ApostolicoandGiancarlo算法、TurboBM算法和ReverseColussi算法。实验的结果表明,QuickSearch算法(BM的一个变种)以及基于后缀自动机的ReverseFactor和TurboReverseFactor算法算是实践中最有效的算法了。ZhuandTakaoka算法和BR算法也是BM的变种,它们则需要O(σ2)的额外空间。 特殊顺序最先达到空间线性最优的是Galil-Seiferas和TwoWay算法,它们把模式分为两部分,先从左到右搜索右边的部分,如果没有失配,再搜索左边的部分。Colussi和Galil-Giancarlo算法将模式位置分为两个子集,先从左至右搜索第一个子集,如果没有失配,再搜索剩下的。Colussi算法作为KMP算法的改进,使得最坏情况下只需要3n/2次比较,而Galil-Giancarlo算法则通过改进Colussi算法的一个特殊情况,把最坏比较次数减少到了4n/3。最佳失配和M最大位移算法分别根据模式的字符频率和首字位移,对模式位置进行排序。SkipSearch,KMPSkipSearch和AlphaSkipSearch算法运用“桶”的方法来决定模式的起始位置。 任意顺序Horspool算法也是BM的一个变种,它使用一种移位函数,而与字符比较顺序不相干。还有其他的变种如:QuickSearch算法,TunedBoyer-Moore算法,Smith算法,Raita算法。 在接下来的章节中,我们会给出上面这些算法的实现。我们把字母表限定为ASCII码或者它的任意子集,编程语言用C,这就意味着数组索引是从0开始,而字符串以NULL结尾。 (第一章完。好像这些算法被挨个夸了个遍,反而不知道该选哪一种了,老外介绍别人的东西时就是这样,尽来虚的。)  二、