kmp演算法的改進

❶ 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演算法的改進擴展閱讀：

KMP演算法是三位學者在 Brute-Force演算法的基礎上同時提出的模式匹配的改進演算法。Brute- Force演算法在模式串中有多個字元和主串中的若干個連續字元比較都相等,但最後一個字元比較不相等時，主串的比較位置需要回退。KMP演算法在上述情況下，主串位置不需要回退,從而可以大大提高效率。

如果模式P與目標T(或其子串)存在某種程度的相似,則認為匹配成功。常用的衡量字元串相似度的方法是根據一個串轉換成另一個串所需的基本操作數目來確定。基本操作由字元串的插入、刪除和替換來組成。

❸ 關於KMP匹配中next[i]數組的改進演算法問題

{ //求KMP演算法中的next函數值，並存入數組next[] int i=1; next[1]=1.在程序中有字元串S和T，你用S[0]代表字元串的長度，但S是字元串，S

❹ 模式p=＇abcaababc ＇的KMP演算法和KMP，並改進演算法的匹配過程！

求子串next[j]值的演算法：
void GetNext(String T, int next[])
{ int j = 1, k = 0;
next[1] = 0;
while(j < len(T)){

if( k == 0 || T[j]==T[k])
{j++; k++; next[j]=k; }
else k = next[k];
}
}
KMP 演算法的自然語言描述
設s為主串，t為模式串，設i為主串s當前比較字元的下標，j為模式串t當前比較字元的下標，令i和j的初值為pos和1。當si = tj時，i和j分別增1再繼續比較；否則 i不變，j改變為next[j]值（即模式串右滑）後再繼續比較。依次類推，直到出現下列兩種情況之一：
一是 j退回到某個j=next[j]值時有si = tj ，則 i和j分別增1後再繼續比較；
二是j退回到j=0時，令主串和子串的下標各增1，隨後比較si和t1 。這樣的循環過程一直進行到變數大於等於s的長度或變數j大於等於t的長度為止。
int KMPIndex(String S, int start,String T, int next[ ])
{
int i = start, j=1;

while ( i <= S[0] && j< T[0]) {
//不失配則繼續比較後續字元
if (j == 0 || S [i] = = T[j] ) {i++; j++ }
//特點：S的i指針不回溯，而且從T的k位置開始匹配
else j=next[j];
}

if (j >= T[0]) return ( i-T(0) );
else return -1;
}

❺ kmp演算法的改進中，改進演算法總是運行不出來！！求幫助。錯誤顯示First-chance exception in zxl.exe: 0xC000

請輸入長串S:1111
請輸入子串T:1
匹配成功，初始匹配成功的位置為第：1個字元
匹配次數為：1
請按任意鍵繼續. . .

我運行OK的啊

❻ kmp演算法難嗎是什麼級別

KMP演算法是我們數據結構串中最難也是最重要的演算法。難是因為KMP演算法的代碼很優美簡潔干練，但裡麵包含著非常深的思維。真正理解代碼的人可以說對KMP演算法的了解已經相當深入了。而且這個演算法的不少東西的確不容易講懂，很多正規的書本把概念一擺出直接勸退無數人。這篇文章將盡量以最詳細的方式配圖介紹KMP演算法及其改進。文章的開始我先對KMP演算法的三位創始人Knuth,Morris,Pratt致敬，懂得這個演算法的流程後你真的不得不佩服他們的聰明才智。

❼ kmp演算法的介紹

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是實現一個next()函數，函數本身包含了模式串的局部匹配信息。

❽ 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);

}

❾ KMP模式匹配演算法是什麼

KMP模式匹配演算法是一種改進演算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出來的，因此人們稱它為「克努特－莫里斯－普拉特操作」，簡稱KMP演算法。此演算法可以在O（n＋m）的時間數量級上完成串的模式匹配操作。其改進在於：每當一趟匹配過程出現字元不相等時，主串指針i不用回溯，而是利用已經得到的「部分匹配」結果，將模式串的指針j向右「滑動」盡可能遠的一段距離後，繼續進行比較。

1.KMP模式匹配演算法分析回顧圖4－5所示的匹配過程示例，在第三趟匹配中，當i＝7、j＝5字元比較不等時，又從i＝4、j＝1重新開始比較。然而，經仔細觀察發現，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1這三次比較都是不必進行的。因為從第三趟部分匹配的結果就可得出，主串中的第4、5和6個字元必然是b、c和a（即模式串第2、第2和第4個字元）。因為模式中的第一個字元是a，因此它無須再和這三個字元進行比較，而僅需將模式向右滑動2個字元的位置進行i＝7、j＝2時的字元比較即可。同理，在第一趟匹配中出現字元不等時，僅需將模式串向右移動兩個字元的位置繼續進行i＝2、j＝1時的字元比較。由此，在整個匹配過程中，i指針沒有回溯，如圖1所示。

圖1改進演算法的模式匹配過程示意

❿ kmp演算法的基本思想

主串：a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b，下文中我們稱作T
模式串：a
b
a
c
a
b，下文中我們稱作W
在暴力字元串匹配過程中，我們會從T[0]
跟
W[0]
匹配，如果相等則匹配下一個字元，直到出現不相等的情況，此時我們會簡單的丟棄前面的匹配信息，然後從T[1]
跟
W[0]匹配，循環進行，直到主串結束，或者出現匹配的情況。這種簡單的丟棄前面的匹配信息，造成了極大的浪費和低下的匹配效率。
然而，在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
比如，在簡單的一次匹配失敗後，我們會想將模式串盡量的右移和主串進行匹配。右移的距離在KMP演算法中是如此計算的：在已經匹配的模式串子串中，找出最長的相同的前綴和後綴，然後移動使它們重疊。
在第一次匹配過程中
T:
a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
在T[5]與W[5]出現了不匹配，而T[0]~T[4]是匹配的，現在T[0]~T[4]就是上文中說的已經匹配的模式串子串，現在移動找出最長的相同的前綴和後綴並使他們重疊：
T:
a
b
a
c
aab
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
然後在從上次匹配失敗的地方進行匹配，這樣就減少了匹配次數，增加了效率。
然而，有些同學可能會問了，每次都要計算最長的相同的前綴會不會反而浪費了時間，對於模式串來說，我們會提前計算出每個匹配失敗的位置應該移動的距離，花費的時間是常數時間。比如：
j012345W[j]abacabF(j)001012當W[j]與T[i]不匹配的時候，設置j
=
F(j-1)
文獻中，朱洪對KMP演算法作了修改，他修改了KMP演算法中的next函數，即求next函數時不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他記修改後的next函數為newnext。顯然在模式串字元重復高的情況下，朱洪的KMP演算法比KMP演算法更加有效。
以下給出朱洪的改進KMP演算法和next函數和newnext函數的計算演算法。