字符串匹配算法BF BM BMH BMHS分析.docVIP

现代网络有哪些信誉好的足球投注网站引擎一般使用基于字符串匹配的有哪些信誉好的足球投注网站方式，使用的软件核心之一是字符串模式匹配算法。网络特别是Internet的信息量极大，在相同的信息采集方式下网络有哪些信誉好的足球投注网站的时间主要取决于所使用的串匹配算法的效率。改善串匹配算法的特性或者时间复杂度，将有效提高网络有哪些信誉好的足球投注网站引擎的性能。所以算法的提出和后续改进的算法称为研究的重点。模式匹配主要有BF算法，KMP算法，BM算法及其改进算法，尤其是BM算法，在实际应用中非常著名，在此我们将对这几种算法做简单分析，分析前，我们做如下假定： 文本： n为文本长度 模式：m为模式长度 2.1 BF算法 BF（Brute Force[2]，这是一种效率很低的算法，其算法主要思想是模式的第一个字符与文本的第一个字符进行比较，如果相同，就继续比较后面的字符，否则，文本的起始位置加1，即模式右移一个位置，再进行比较，如果模式与文本中一段连续字符串都相同，则匹配成功，返回当时文本的起始比较位置，否则匹配不成功，实现过程：在串和串中比较的起始下标i和j；循环直到中所剩字符小于的长度或的所有字符均比较完（如果[i]=pat[j]，则继续比较和的下一个字符；否则将i和j回溯，准备下趟比较）；如果中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。 BF Algorithm BF k=0;j=0; while ((j=m)(k=n-m)) { if (pat[j]==text[k]) { k++; j++; } Else { k=k-j+1;j=0; } } if (j= =m) Match found at text[k-m] else No match found 例子 1： 文本： astringsearchingexamplelienvolingrelatively 模式串：relative 1. astringsearchingexamplelienvolingrelatively relative 2. astringsearchingexamplelienvolingrelatively relative 3. astringsearchingexamplelienvolingrelatively relative 4. astringsearchingexamplelienvolingrelatively relative ： 32. astringsearchingexamplelienvolingrelatively relative 该算法简单，但是效率较低。时间复杂度：设匹配成功发生在处，则在i-1趟不成功的匹配中比较了（i-1）m次，第i趟成功匹配共比较了m次，所以总共比较了im次，因此平均比较次数是： 2.2 KMP算法 由Knuth 等人提出的Knuth-Morris-Praa(KMP)算法是对BF算法的很大改进，每次匹配失败时利用已经得到的“部分匹配”结果，将模式串向右移动若干位置后继续比较 KMP算法的基本思想：将文本text和模式pat左端对齐进行比较，匹配text[i]和pat[j]时:若text[i]=pat[j]，则继续往前匹配比较;若text[i]pat[j]，则文本中i不变，模式中j指向next[j]所指示位置。这可以提高匹配算法的效率，但相对比较复杂。KMP算法与BF算法在形式上极为相似。不同之处在于：当匹配过程中产生“失配”时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退至零时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第一个字符不等，应从主串的第i+1个字符起重新进行匹配。实现过程：在串和串中比较的起始下标i和j；循环直到中所剩字符小于的长度或T的所有字符均比较完（如果[i]=pat[j]，则继续比较和的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0，则将i和j分别+1，准备下趟比较）；如果中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。Algorithm KMP int KMP(char text[ ],char pat[ ],int next[ ] ) { int i=0,j=0; n=len(text);m=len(pat); while(in jm) if (j= =-1||pat[j]==text[i]) {i++;j++;} else j=next[j] if(j=m)return i-m; else return 0; } 数组next[