① 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演算法問題
k＝nextval[k]的意思是指當模式串(即T串)與主串(即S串)發生失配時，這個k應當指示前綴指針應當回溯到哪個位置。
比如，有下面的匹配表值
next值 :001012
假設k當前等於2時，那麼如果此時模式串與主串發生失配時，就有k=nextval[2]=1，即模式串與主串匹配到第2個字元時發生失配，那麼後綴指針無需回溯，前綴指針只需回溯到第1個字元的位置並且繼續與主串的第2個字元匹配。這樣就可以加快匹配的速度，因為後綴指針不用再回溯。即教材所說的後綴指針盡量向右側滑動。
③ 數據結構中KMP演算法為什麼避免了不必要的回溯
因為它對匹配串也就是子串做了一個數組記錄每個字元的值，每次匹配不成功時就查看對應的值，然後移動母串指針，解決問題的關鍵就是對匹配串做了標記值。
④ kmp演算法的最大特點是指示主串的指針不需要回溯 A.正確 B.錯誤
個人理解，應該是B.錯誤
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
⑥ 模式識別KMP演算法,懂計算機的朋友幫幫忙
學過數據結構的人，都對KMP演算法印象頗深。尤其是新手，更是難以理解其涵義，搞得一頭霧水。今天我們就來面對它，不將它徹底搞懂，誓不罷休。
如今，大夥基本上都用嚴蔚敏老師的書，那我就以此來講解KMP演算法。(小弟正在備戰考研，為了節省時間，很多課本上的話我都在此省略了，以後一定補上。)
嚴老的《數據結構》79頁講了基本的匹配方法，這是基礎。先把這個搞懂了。
80頁在講KMP演算法的開始先舉了個例子，讓我們對KMP的基本思想有了最初的認識。目的在於指出「由此，在整個匹配的過程中，i指針沒有回溯，」。
我們繼續往下看：
現在討論一般情況。
假設 主串：s: 『s(1) s(2) s(3) ……s(n)』 ; 模式串 ：p: 『p(1) p(2) p(3)…..p(m)』
把課本上的這一段看完後，繼續
現在我們假設 主串第i個字元與模式串的第j(j<=m)個字元『失配』後，主串第i個字元與模式串的第k(k<j)個字元繼續比較
此時，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我們得到關系式
『p(1) p(2) p(3)…..p(j-1)』 = 』 s(i-j+1)……s(i-1)』
由於s(i)≠p(j)，接下來s(i)將與p(k)繼續比較，則模式串中的前(k-1)個字元的子串必須滿足下列關系式，並且不可能存在 k』>k 滿足下列關系式：(k<j),
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(i-k+1)s(i-k+2)……s(i-1)』
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比較)
匹配串： P(1) p(2) …… p(k-1) p(k)
現在我們把前面總結的關系綜合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比較)
P(1) p(2) ……. p(k-1) p(k)
由上，我們得到關系：
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(j-k+1)s(j-k+2)……s(j-1)』
接下來看「反之，若模式串中存在滿足式(4-4)。。。。。。。」這一段。看完這一段，如果下面的看不懂就不要看了。直接去看那個next函數的源程序。(偽代碼)
K 是和next有關系的，不過在最初看的時候，你不要太追究k到底是多少，至於next值是怎麼求出來的，我教你怎麼學會。
課本83頁不是有個例子嗎？就是 圖4.6
你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。
然後找幾道練習題好好練練，一定要做熟練了。現在你的腦子里已經有那個next演算法的初步思想了，再回去看它是怎麼推出來的，如果還看不懂，就繼續做練習，做完練習再看。相信自己！！！
附：
KMP演算法查找串S中含串P的個數count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T[i]!=T[j+1]&& j>=0 )
j=next[j] ; //遞推計算
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函數求T在主串S中的個數count的KMP演算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
⑦ 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演算法的說明有什麼
（1）未改進的模式匹配演算法的時間復雜度為O（nm），但在一般情況下，其實際的執行時間接近O（n＋m），因此至今仍被採用。
（2）KMP演算法僅當模式與主串之間存在許多「部分」匹配的情況下才顯得比未改進的模式匹配快。
（2）KMP演算法的最大特點是指示主串的指針不需要回溯，在整個匹配過程中，對主串僅需要從頭至尾掃描一遍，這對處理存儲在外存上的大文件是非常有效的。
⑨ 演算法-KMP
大一下參加學校ACM預備隊集訓的時候首次接觸KMP演算法，當時看了很多介紹文章，仍然不是很理解其實質，只是簡單地套模板AC題目，待大二數據結構與演算法課堂上再聽老師介紹一次，才恍然大悟其實KMP也就是那麼回事嘛。但當初為啥看那麼多文章都沒弄明白呢？正巧最近和朋友聊天時他告訴我他對KMP不是很理解，於是打算自己寫一篇文章，鞏固自己對KMP的認識，也希望能夠幫助更多朋友理解KMP。
在開始之前，需要知曉的概念：
前綴：以原串串頭為自身串頭的子串，如 的前綴有：
後綴：以原串串尾為自身串尾的子串，如 的後綴有：
注意：字元串前後綴都不包括該串本身
給你一個文本串T(Text String)
再給你一個模式串P(Pattern String)
問該模式串是否在文本串中，怎麼找？
一開始只好分別從文本串與模式串的串頭開始逐字母比較
二者相同，再比較T串與P串的下一位
如此反復
如果一直這么順利，兩串對應位置的字元總相同，待P串中最後一個字元也匹配完畢，說明該模式串在文本串中存在，耶( •̀ ω •́ )y超開心，查找結束。但，大多數匹配過程不會如此順利，在該例中，當匹配進行至
很明顯，失配了。現在怎麼辦？按樸素思想，將P串相對T串整體右移一位，重新開始匹配，即
但這種演算法效率無疑是十分低下的。設T串長度N，P串長度M，則樸素演算法時間復雜度為O(MN)
已知的重要信息並沒有被使用——已匹配的字元串前綴
在上例中，當P串最後一個字元匹配失敗時，其已有包含七個字元的 前綴子串S 匹配成功
完全可以利用前綴子串S做點什麼。觀察到在S串
中，有相同前後綴，即下圖藍色部分
而S串各字元又與T串中對應字元相同，即有
當失配發生後，直接將P串右移四位使S串藍色後綴部分對齊T串中藍色前綴部分
從圖中紅框部分繼續嘗試匹配，發現再次失配。這次，已匹配成功的前綴串S為
而在該串中沒有相同的前後綴，只能將P串串頭移至失配處進行比較
再次失配。此時前綴串S為空串，只好如樸素演算法般將P串整體右移一位，重新開始比較
匹配成功。於是又按照之前的步驟往下匹配，直至再次失配或匹配成功
後續步驟同上，不再贅述
上述示例已展現，KMP演算法的精髓在於對已匹配成功的前綴串S的利用
在樸素演算法中，匹配失敗了，T串待匹配字元會回溯
T串原本已匹配至T[7] = 'X'，但是因為失配，需回溯到T[1] = 'b'重新開始匹配
而在KMP演算法中，若P[M]與T[K]匹配失敗，K不會回溯。既然匹配過程是從T[0]開始逐漸向右進行的，至T[K]失配發生時，T[0]至T[K-1]早已匹配過，何必再回溯過去重復匹配呢？於是乎，就如問題引入部分展示般
每當失配發生，我們總是去關注P串中已匹配成功的前綴串S
因為該前綴串是匹配成功的，說明在T串中必定存在與該前綴串相同的子串，記為S'
若S串中存在相同前後綴
則S'串必然也存在此相同前後綴
所以只需將P串右移四位，使得S串的該相同前綴對齊S'串的該相同後綴
再嘗試比較T[7]與P[3]
至於T[7]與P[3]是否能夠匹配另說（當然，本例中一看就知道沒匹配上），但通過對前綴串S的利用，成功省去了P串右移一位、兩位和三位後的無效匹配
繼續深入思考，給定一個具體的P串，其第N位的前綴串S內容是固定的，則S是否存在相同前後綴、相同前後綴的長度與內容也是確定的。換言之，對於一個具體的P串，當其與給定T串匹配至P[N]失配，P串應右移幾位再次與T串進行匹配也是確定的。我們完全可以使用一個數組記錄當P[N]失配後，應當使用N之前的哪一位再來與T串進行匹配，以此提高匹配效率，記該數組為Next數組
定義Next[i] = j表示當P串中第i位失配後，跳轉至P串第j位再次嘗試匹配
還是以之前的P串為例，它的Next數組求出來應為
取下標5為例，其前綴串為
最長相同前後綴為
若P[5]失配，應跳轉至P[1]再次嘗試匹配（最長相同前綴對應P[0]，則取其後一位P[1]，若存在多位，則取最後一位的下一位），P[5]的前一個字元P[4]對應字元'a'，而P[1]前一個字元P[0]同對應字元'a'，保證了P[1]之前字元與T串中對應字元保持匹配。所以Next[5] = 1，其餘下標對應Next數組值同如此求。
特別地，規定Next[0] = -1。而對於除下標0外的任意下標N，Next[N]的含義是 前N-1個已匹配成功的字元構成的前綴串S中，最長相同前後綴長度。 所以若在下標為N處匹配失敗了，則應前往Next[N]所對應的下標處匹配。
具體地，以下圖所示為例，P[6]與T[6]失配
而Next[6] = 2，所以使用P[2]再次嘗試與T[6]進行匹配
當求出P串Next數組後，便可快速進行與T串的匹配
現在問題只剩下如何求Next數組，注意到Next數組既然只與P串本身相關，與文本串T無關，故令P串與自身匹配即可求得
考慮字元串
其Next數組應為
令其與給定文本串相匹配
當匹配進行至
失配，於是跳轉至P[Next[3]] = P[1]處再次嘗試匹配
再度失配，也必然失配
問題在於不該出現P[N] =P[Next[N]]
若P[N] =P[Next[N]]，則P[N]失配後使用P[Next[N]]再次嘗試匹配，由於P[N] =P[Next[N]]，P[N]匹配失敗，P[Next[N]]必然也失敗
因此，若出現P[N] =P[Next[N]]情況，則令Next[N]=Next[Next[N]]
本例中該字元串新Next數組為
當匹配進行至
失配，於是跳轉至P[Next[3]] = P[0]處再次嘗試匹配
省去了之前跳轉至P[1]處的無效匹配
設T串長度M，P串長度N，由於KMP演算法不會回溯，分析易知時間復雜度為O(m+n)
對於P[N]，若其前綴串S含相同前後綴F，且F長度為n（n>1），Next[N]可以取1至n中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間