文档介绍：串匹配算法戴正华Contents串匹配算法 1第一章引言 2第一节 2第二节 2第二章精确串匹配算法 3引论精确串匹配算法的分类 3第一节 单模式串匹配算法 3第二节 多模式串匹配算法 20第三章 近似串匹配算法 27第一节 引言 27第二节 动态规划算法 28第三节 基于自动机的串匹配算法 35第四节 位并行串匹配算法 37第五节 过滤算法与index 41小结 42参考文献 43附录A算法源码 451BM算法 452BMH算法 463BMHS算法 47A6自动机算法 47A7bom算法 48A8shift-or算法 50A9BNDM算法 51A10哈希法 51第一章引言 第一节 第二节1970年MP算法【MorrisPratt1970】。在窗口w(s)内,从最右字符开始自左向右扫描目标串,遇到不匹配的字符根据预先计算好的两个表:良好后缀跳转表Bmbc和不良字符跳转表Bmbc来决定窗口滑动的距离。设当前窗口w(s)的起始位置为j,P[i+1…i+m-1]=T[j+i+1…j+m-1]=u,P[i]!=T[j+i].T[j+I]=b,P[I]=:如果u出现在P中两次或多次,即有P[i+1…m-1]=P[k…k+m-i-2](k<i+1)例如: 如果u没有在P中再次出现,但u的后缀v是P的前缀那么例如:不良字符跳转有如下两种情况:字符T[j+i]=b出现在P中例如:字符b未出现在P中良好后缀跳转函数是一个定义域为模式串字符位置,值域为正整数的函数,存放在大小为模式串长度m的数组Bmgc[m]中,bmGc[i]表示当P[i+1…m-1]与当前文本匹配而P[I]不匹配时窗口移动的距离。设对任意的k,I<k<m,当s>=k或x[k-s]=x[k]时Cs(I,s)为真。如果s<I时x[I-s]!=x[I]则Co(I,s)为真。那么,bmGs[I+1]=min{s>0:Cs(I,s)andCo(I,s)}。在计算过程中定义了数组suff[m],定义如下:suff[I]=max{k:x[I-k+1…I]=x[m-k…m-1](0<I<m)。不良字符转移函数是定义域为字符集中所有字符,值域为正整数的函数,存放在大小为字符集大小的数组bmBc[]中,定义如下:如果c出现在P中则bmBc[c]=min{I:0<I<m-1andx[m-1-I]=c}否则bmGc[c]=m。例如:I01234567P[i]CAGACACASuff[i]02010308BmGc[i]AGTBmBc[c]1258bm算法伪码描述如下: voidBm_Match(char*P,intn){i=0;//文本当前的匹配位置j=0;//模式串当前的匹配位置while(j<=n-m){i=m-1;while(i>=0&&T[j+i]==P[i])//匹配i--;if(i<0){匹配成功;j+=bmGc[0];}Elsej+=max(bmGc[i],bmBc[T[j+i]]-m+1+i);}}Bm算法源码:[]和bmBc[]的时间,需要o(m+σ)。需要额外的空间为o(m+σ)。在最好的情况下时间为o(n/m),最坏情况下时间复杂度为o(m+n),平均时间复杂度为:o(n/m)【MikeLiddell1997】,适合大字符集的应用。-(BMH)[.,1980]算法bm算法中的不良字符跳转函数对于小字符集(例如生物信息处理中表示DNA分子的字符集)应用而言并不能取得很好的效率,但是如果字符集相对于模式串P很大(例如ASIIC码),将会取得非常好的效果。正是基于这一点Horspool改进了bm算法,算法只使用了不良字符跳转表bmBc[]。预处理过程需要o(m+σ)的时间,o(σ)的空间。时间复杂度为o(mn)。但是平均时间复杂度要优于bm算法。BMH算法:(BMHS)【】。BMHS算法同样只用到不良字符跳转表。注意这样一个事实:丛窗口w(k)到w(k+1)至少要移动一个字符。BMH算法用窗口w(k)的最右字符T[j+m-1]来计算跳转距离,Sunday该为用T[j+m]来计算跳转距离。跳转的最大步长由BMH算法的m-1增加为m。跳转函数qsBc[c]定义如下:forcin,qsBc[c]