改進的kmp演算法

❶ 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演算法之所以叫做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演算法的時間復雜度為什麼是O(n)

主串T，比較串P，
由於KMP演算法的思想是主串不回溯的簡化演算法，執行的時候呢在串比較的掃描裡面要麼執行POST和POSP，要麼執行NEXT[]數組的右移，然後比較，所以字元比較最多就是為O（LenthT）,即不會超過O（n）
其實KMP看起來很嚇人，但是你抓住它的思想「主串不回溯」就很簡單了.

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

❹ 字元串匹配演算法的基本思想是什麼

這個用到了正規表達式對字元串的匹配.程序如下,是javascript的.
<script language="javascript">
function check(obj)
{var str=/^[0-9]{4}-[0-9]{7}$/ig;
if(str.test(obj))
alert("this is your number");
else
alert("write again");}
</script>
<form name="form1">
<input type="text" name="mytext" size="12">
<input type="button" value="click" onclick="check

(form1.mytext.value)">
</form>
要求輸入的是標准電話號碼.看不懂問我.呵呵.

❺ 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模式匹配演算法
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與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是根據給定的模式串W1,m,定義一個next函數。next函數包含了模式串本身局部匹配的信息。
完全掌握KMP演算法思想
學過數據結構的人，都對KMP演算法印象頗深。

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

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

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

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

❾ 什麼是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