kmp算法和bm算法效率

㈠ kmp算法什么意思

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0时，表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

㈡ 什么情况下，KMP算法的性能会退化为朴素匹配算法

（1）未改进的模式匹配算法的时间复杂度为O（nm），但在一般情况下，其实际的执行时间接近O（n＋m），因此至今仍被采用。

（2）KMP算法仅当模式与主串之间存在许多“部分”匹配的情况下才显得比未改进的模式匹配快。

（2）KMP算法的最大特点是指示主串的指针不需要回溯，在整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理存储在外存上的大文件是非常有效的。

(2)kmp算法和bm算法效率扩展阅读：

KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时，主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退,从而可以大大提高效率。

如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成。

㈢ kmp算法详解

KMP模式匹配算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。
求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。
include "string. h"

#include<assert. h>

int KMPStrMatching(String T, String P, int. N, int startIndex)

{int lastIndex=T.strlen() -P.strlen();

if((1 astIndex- startIndex)<0)//若 startIndex过大,则无法匹配成功

return (-1);//指向P内部字符的游标

int i;//指向T内部字符的游标

int j=0;//指向P内部字符的游标

for(i= startIndex; i <T.strlen(); i++)

{while(P[j]!=T[i]&& j>0)

j=N[j-1];

if(P[j]==T[i])

j++;

if(j ==P.strlen())

return(1-j+1);//匹配成功,返回该T子串的开始位置

}

return (-1);

}

㈣ 在Word编辑中，模式匹配查找中能使用的通配符是

在Word编辑中，模式匹配查找中能使用的通配符是：*和?。

模式匹配，数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。

假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。

(4)kmp算法和bm算法效率扩展阅读

算法思想：从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。

若模式子串的长度是m,目标串的长度是n，这时最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法的时间复杂度为O(mn)。

朴素的模式匹配算法中存在回溯，这影响到匹配算法的效率，因而朴素的模式匹配算法在实际应用中很少采用。在实际应用主要采用无回溯的匹配算法，KMP算法和BM算法均为无回溯的匹配算法。

㈤ bm，horspool，sunday，kmp，kr，ac算法哪个效率最高

玩锝地方多，
但实在锝地方狠仯了

㈥ 我的KMP算法做出来了，可是居然运行时间比普通匹配还慢求高手解答，帮忙修改一下！

①你的KMP代码里很多东西导致KMP算法变慢：
1、计算主字符串长度很浪费时间，可以不用计算的，事先开辟一个大空间。
2、new int[len+1];很浪费时间，事先开辟大空间，或者用多级内存管理。
3、delete []next很浪费时间。

②但是①说的不是本质，真正的原因是：KMP的优点是避免重复匹配的记忆功能，缺点是启动慢构造next，这就导致如果要被匹配的主字符串太短（少于1k个字符都算短的）。
而朴素算法启动不需要时间。

③另一方面，你的main中主字符串和匹配字符串没有相似性（只在最后2个字符串才进行了一次大的返回），而KMP的优点就在于处理相似字符串匹配，相似度越高，字符串越长，匹配效果越好。

④我改了下你的代码，增加的主字符串的长度，提高了字符串相似程度，结果就是KMP的时间比朴素算法要好接近30%：
Time to do Index loops is 32.031
Time to do KMP loops is 23.609

⑤代码如下：

#include<time.h>
#include <iostream.h>
#include <string.h>
int Index_BF ( char S [ ], char T [ ], int pos )
{
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
j ++;
else
{
i ++; j = 0; }
if ( T[j] == '\0')
return i;
else
return -1;
}
void get_nextval(const char *T, int next[])
{
int j = 0, k = -1;
next[0] = -1;
while ( T[j/*+1*/] != '\0' )
{
if (k == -1 || T[j] == T[k])
{
++j; ++k;
if (T[j]!=T[k])
next[j] = k;
else
next[j] = next[k];
}// if
else
k = next[k];
}

}

int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1;//空指针或空串，返回-1。

static int next[50];
get_nextval(Pattern,next);//求Pattern的next函数值

static int index,i,j;
index=i=j=0;
for(;Text[i]!='\0' && Pattern[j]!='\0';)
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}

//delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功
else
return -1;
}

int main()//abCabCad
{
int i;

char* text= "jirjhirjgijerigjir\
rgr\
jirjhirjgijerigjir\
rgr\
jirjhirjgijerigjir\
dCadtttccadCadCadtttcc\
dtttccadCadCadtttcc\
\
jgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreigfgergregegrgergegirjgirjgirjigjierjgijjgirejgijreijgirejgijreirighrjigjeigjadCadCadjreigjrijgirejgijreigfgergrege\
adCadCadtttccctctc";

char*pattern="adCadCadtttccctctc";

clock_t start, finish;
double ration;
//普通匹配算法
cout<<( "Time to do Index loops is ") ;
start = clock();
for(int k=0;k<50000;k++)
{
i=Index_BF(text,pattern,1);

}
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<( "%f seconds\n", ration )<<endl;
//KMP匹配算法
cout<<( "Time to do KMP loops is ")<<endl;
start = clock();
for(int j=0;j<50000;j++)
{
i=KMP(text,pattern);
}
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<( "%f seconds\n", ration )<<endl;

cin>>finish;
return 0;

}

㈦ 帮忙解答一道简单的BM算法的题目

入侵检测系统中模式匹配算法的研究
摘要 入侵检测是网络安全的最后一道防线，模式匹配算法是基于特征匹配的入侵检测系统中的核心算法，模式匹配的效率决定这类入侵检测系统的性能。本文对入侵检测系统中的模式匹配算法进行了综述，包括经典的单模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法。对各种算法的性能进行了分析。最后提出了改进模式匹配算法效率的研究方向。
关键词: 网络安全；入侵检测；模式匹配；多模式匹配

全文见

㈧ 指出BM算法与KMP算法的区别

KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。
1、因为路由表中的每个表项都指定了一个网络，所以一个目的地址可能与多个表项匹配。最明确的一个表项，即子网掩码最长的一个，就叫做最长前缀匹配。
2、之所以这样称呼它，是因为这个表项也是路由表中，与目的地址的高位匹配得最多的表项。

㈨ 什么时候用bf算法好，什么时候用kmp算法好

如果待匹配的模式串中重复的字符很少，用bf就OK了，正常的字符串差不多都是这样的
在模式串中有很多重复的子串时，kmp效率比bf高很多

㈩ 各位面过BAT的同学,你们有没有被考过KMP算法

三家都面过，也许是我运气好，没有碰到过。其实KMP算法效率不是很高，理解起来也不容易。如果面试官跟你聊字符串匹配算法，你完全可以说点其他算法装逼。给你一个网页，希望能帮助到你。4795369请采纳最佳答案~