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請採納最佳答案~