字符串匹配算法bfbmbmhbmhs分析

《字符串匹配算法bfbmbmhbmhs分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、现代网络搜索引擎一般使用基于字符吊匹配的搜索方式，使用的软件核心之一是字符串模式匹配算法。网络特别是Internet的信息量极大，在相同的信息采集方式下网络搜索的时间主要取决于所使用的串匹配算法的效率。改善串匹配算法的特性或者时间复杂度，将有效提高网络搜索引擎的性能。所以算法的提出和后续改进的算法称为研究的重点。模式匹配主要有BF算法，KMP算法，BM算法及其改进算法，尤其是BM算法，在实际应用中非常著名，在此我们将对这几种算法做简单分析，分析前，我们做如下假定：文本：text[O..n-]n为文本长度模式：为模式长度2.1BF算法BF(BruteForce)算法又称为蛮力匹配

2、算法[2],这是一种效率很低的算法,其算法主要思想是模式的第一个字符与文木的第一个字符进行比较，如果相同，就继续比较后面的字符，否则，文本的起始位置加1,即模式右移一个位置，再进行比较，如果模式与文本中一段连续字符串都相同，则匹配成功，返回当时文本的起始比较位置，否则匹配不成功，实现过程：在串text和串pat屮比较的起始下标i和j;循环直到text中所剩字符小于pat的长度或pat的所有字符均比较完(如果text[i]=pat[j],则继续比较text和pat的下一个字符；否则将i和j回溯,准备下趟比较)；如果pat中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失

3、败，返回0。BF算法如下：AlgorithmBFk=O;j=O;while((j<=m)&&(k<=n-m)){if(patUJ=text[k]){k卄；j卄；}Elsek=k-j+l;j=O;讦（j==m）Matchfoundattcxt[k-m]elseNomatchfound例子1:文木：astringsearchingexamplelienvolingrelatively模式串：relative1.astringsearchingexamplelienvolingrelativelyrelative2.astringsearchingexamplelienvolingre

4、lativelyrelative3・astringsearchingexamplelienvolingrelativelyrelative4.astringsearchingexamplelienvolingrelativelyrelative■32.astringsearchingexamplelienvolingrelativelyrelative该算法简单，但是效率较低。时间复杂度：设匹配成功发生在text[i]处，则在i・l趟不成功的匹配中比较了(i-1)xm次，第i趟成功匹配共比较了m次，所以总共比较了ixm次，因此平均比较次数是：m*(n-m+l)/2o最坏情况下要进

5、行m*(n・m+l)次比较，时间复杂度为O(m*n)。2.1KMP算法由Knuth等人提出的Knuth-Morris-Praa(KMP)算法⑵是对BF算法的很大改进，每次匹配失败时利用已经得到的“部分匹配"结果，将模式串向右移动若干位置后继续比较。KMP算法的基本思想:将文本text和模式pat左端对齐进行比较，匹配text[i]和patfj]时:若text[i]=pat[j],则继续往前匹配比较;若text[i]^pat[j],则文本中i不变，模式屮j指向next[j]所指示位置。这可以提高匹配算法的效率，但相对比较复杂。KMP算法与BF算法在形式上极为相似。不同之处在于：当匹

6、配过程中产牛“失配”时，指针i不变，指针j退回到nextfj]所指示的位置上重新进行比较，并且当指针j退至零时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第一个字符不等，应从主串的第i+1个字符起重新进行匹配。实现过程：在串text和串pat中比较的起始下标i和j；循环直到text中所剩字符小于pat的长度或T的所有字符均比较完(如果text[i]=pat[j],贝lj继续比较text和pat的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0,则将i和j分别+1,准备下趟比较)；如果pat中所有字符均比较完，则匹配成功，返回匹配的起始

7、下标；否则匹配失败，返回0。具体算法如下：AlgorithmKMPintKMP(chartext[],charpat[],intnext[]){inti=0,j=0;n=len(text);m=len(pat);while(i

8、

9、pat[j]=text[i]){i卄;j卄;}elsej=next[j]if(j>=m)returni-m;elsereturn0;}数组next[j]表示当模式中第j个字符与止文中相应字符匹配失败时，在模式中需要一个新的