改進kmp演算法的優點

㈠ kmp演算法的介紹

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

㈡ 關於KMP演算法的說明有什麼

（1）未改進的模式匹配演算法的時間復雜度為O（nm），但在一般情況下，其實際的執行時間接近O（n＋m），因此至今仍被採用。

（2）KMP演算法僅當模式與主串之間存在許多「部分」匹配的情況下才顯得比未改進的模式匹配快。

（2）KMP演算法的最大特點是指示主串的指針不需要回溯，在整個匹配過程中，對主串僅需要從頭至尾掃描一遍，這對處理存儲在外存上的大文件是非常有效的。

㈢ KMP演算法的主要特點是什麼

kmp演算法主要是減少字元串查找過程中的回退，盡可能減少不用的操作，演算法復雜度是O(n+m)。思想可以使用與ac自動機。主要是先求next數組。比如當next[i] = j。也就是說0 ~ j-1所在的字元串跟i-j 到 i-1 所在的字元串是相同的。其他的原理基本一樣。 你可以看看http://ke..com/view/659777.htm

㈣ KMP是什麼意思

一種由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人設計的線性時間字元串匹配演算法。這個演算法不用計算變遷函數δ，匹配時間為Θ（n），只用到輔助函數π[1，m]，它是在Θ（m）時間內，根據模式預先計算出來的。數組π使得我們可以按需要，「現場」有效的計算（在平攤意義上來說）變遷函數δ。粗略地說，對任意狀態q=0，1，…，m和任意字元a∈Σ，π[q]的值包含了與a無關但在計算δ（q，a）時需要的信息。由於數組π只有m個元素，而δ有Θ（m∣Σ∣）個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。

㈤ kmp演算法的優化

KMP演算法是可以被進一步優化的。
我們以一個例子來說明。譬如我們給的P字元串是「abcdaabcab」，經過KMP演算法，應當得到「特徵向量」如下表所示： 下標i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 但是，如果此時發現p(i) == p(k），那麼應當將相應的next[i]的值更改為next[k]的值。經過優化後可以得到下面的表格： 下標i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 優化的next[i] -1 0 0 0 -1 1 0 0 3 0 （1）next[0]= -1 意義：任何串的第一個字元的模式值規定為-1。
（2）next[j]= -1 意義：模式串T中下標為j的字元，如果與首字元
相同，且j的前面的1—k個字元與開頭的1—k
個字元不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=」abCabCad」 則 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意義：模式串T中下標為j的字元，如果j的前面k個
字元與開頭的k個字元相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意義：除（1）（2）（3）的其他情況。
補充一個next[]生成代碼： voidgetNext(constchar*pattern,intnext[]){next[0]=-1;intk=-1,j=0;while(pattern[j]!=''){while(k!=-1&&pattern[k]!=pattern[j])k=next[k];++j;++k;if(pattern[k]==pattern[j])next[j]=next[k];elsenext[j]=k;}} PROGRAMImpl_KMP;USESCRT;CONSTMAX_STRLEN=255;VARnext:array[1..MAX_STRLEN]ofinteger;str_s,str_t:string;int_i:integer;Procereget_next(t:string);Varj,k:integer;Beginj:=1;k:=0;whilej<Length(t)dobeginif(k=0)or(t[j]=t[k])thenbeginj:=j+1;k:=k+1;next[j]:=k;endelsek:=next[k];end;End;Functionindex(s:string;t:string):integer;Vari,j:integer;Beginget_next(t);index:=0;i:=1;j:=1;while(i<=Length(s))and(j<=Length(t))dobeginif(j=0)or(s[i]=t[j])thenbegini:=i+1;j:=j+1;endelsej:=next[j];ifj>Length(t)thenindex:=i-Length(t);end;End;BEGINClrScr;{清屏，可不要}Write('s=');Readln(str_s);Write('t=');Readln(str_t);int_i:=index(str_s,str_t);ifint_i<>0thenbeginWriteln('Found''',str_t,'''in''',str_s,'''at',int_i,'.');endelseWriteln('Cannotfind''',str_t,'''in',str_s,'''.');END.index函數用於模式匹配，t是模式串，s是原串。返回模式串的位置，找不到則返回0

㈥ 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演算法詳解

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演算法的基本思想

主串：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函數的計算演算法。

㈨ 什麼是KMP演算法

KMP就是串匹配演算法
運用自動機原理
比如說
我們在S中找P
設P＝{ababbaaba}
我們將P對自己匹配
下面是求的過程:{依次記下匹配失敗的那一位}
[2]ababbaaba
......ababbaaba[1]
[3]ababbaaba
........ababbaaba[1]
[4]ababbaaba
........ababbaaba[2]
[5]ababbaaba
........ababbaaba[3]
[6]ababbaaba
..............ababbaaba[1]
[7]ababbaaba
..............ababbaaba[2]
[8]ababbaaba
.................ababbaaba[2]
[9]ababbaaba
.................ababbaaba[3]
得到Next數組『0,1,1,2,3,1,2,2,3』
主過程：
[1]i:=1 j:=1
[2]若(j>m)或(i>n)轉[4]否則轉[3]
[3]若j=0或a[i]=b[j]則【inc(i)inc(j)轉[2]】否則【j:=next[j]轉2】
[4]若j>m則return(i-m)否則return -1;
若返回－1表示失敗，否則表示在i-m處成功
若還不懂mail:[email protected]

參考一下這里吧:

http://www.chinaaspx.com/archive/delphi/4733.htm

㈩ 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，繼續進行比較。