院系： 計算機科學技術學院
班級： 軟體11-2
姓名： 張萌
學號： 20111702010235
指導教師賀薪宇
2023年11月10日
kmp演算法對於任何模式和目標序列，都可以**性時間內完成匹配查詢，而不會發生退化，是乙個非常優秀的模式匹配演算法。但是由於kmp演算法在構造跳轉表next過程中進行了多個層面的優化和抽象，使得kmp演算法進行模式匹配的原理較難理解。本文能夠深入kmp演算法，分析演算法各個細節。
kmp演算法模式函式值 next陣列
1 程式的功能設計 1
2 程式的資料設計 2
3 程式的函式設計 3
4 函式程式設計及除錯 4
5 整體除錯 5
6 總結 6
參考文獻 7
致謝 8
cook於2023年證明的乙個理論得到，任何乙個可以使用被稱為下推自動機的計算機抽象模型來解決的問題，也可以使用乙個實際的計算機（更精確的說，使用乙個隨機訪問機）在與問題規模對應的時間內解決。特別地，這個理論暗示存在著乙個演算法可以在大約m+n的時間內解決模式匹配問題，這裡m和n分別是儲存文字和模式串陣列的最大索引。knuth和pratt努力地重建了cook的證明，由此建立了這個模式匹配演算法。
大概是同一時間，morris在考慮設計乙個文字編輯器的實際問題的過程中建立了差不多是同樣的演算法。這個演算法就是kmp演算法。kmp演算法是一種改進的字串匹配演算法，由與和同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱kmp演算法）。
kmp演算法的關鍵是根據給定的模式串w1,m,定義乙個next函式。next函式包含了模式串本身區域性匹配的資訊。
kmp演算法的核心思想是利用已經得到的部分匹配資訊來進行後面的匹配過程。
假設在模式匹配的程序中，執行t[i]和w[j]的匹配檢查。若t[i]=w[j]，則繼續檢查t[i+1]和w[j+1]是否匹配。若t[i]不等於w[j]，則分成兩種情況：
若j=1，則模式串右移一位，檢查t[i+1]和w[1]是否匹配；若1 在介紹kmp演算法之前，先介紹一下bf演算法。
bf演算法是普通的模式匹配演算法，bf演算法的思想就是將目標串s的第乙個字元與模式串p的第乙個字元進行匹配，若相等，則繼續比較s的第二個字元和p的第二個字元；若不相等，則比較s的第二個字元和p的第乙個字元，依次比較下去，直到得出最後的匹配結果。
將主串s中某個位置i起始的子串和模式串t相比較。即從j=0起比較s[i+j]與t[j]，若相等，則在主串s中存在以i為起始位置匹配成功的可能性，繼續往後比較(j逐步增1)，直至與t串中最後乙個字元相等為止，否則改從s串的下乙個字元起重新開始進行下一輪的匹配，即將串t向後滑動一位，即i增1，而j退回至0，重新開始新一輪的匹配。
在串s=「abcabcabdabba」中查詢t=「abcabd」（我們可以假設從下標0開始）:先是比較s[0]和t[0]是否相等，然後比較s[1]和t[1]是否相等。我們發現一直比較到s[5]和t[5]才不等。
如圖：當這樣乙個失配發生時，t下標必須回溯到開始，s下標回溯的長度與t相同，然後s下標增1,然後再次比較。如圖：
這次立刻發生了失配，t下標又回溯到開始，s下標增1,然後再次比較。如圖：
又一次發生了失配，所以t下標又回溯到開始，s下標增1,然後再次比較。這次t中的所有字元都和s中相應的字元匹配了。函式返回t在s中的起始下標3。如圖：
還是相同的例子，在s=」abcabcabdabba」中查詢t=」abcabd」，如果使用kmp匹配演算法，當第一次搜尋到s[5]和t[5]不等後，s下標不是回溯到1，t下標也不是回溯到開始，而是根據t中t[5]==『d』的模式函式值，直接比較s[5]和t[2]是否相等，因為相等，s和t的下標同時增加;因為又相等，s和t的下標又同時增加。最終在s中找到了t。如圖：
在前面的例子。t[5]==『d』的模式函式值等於2（next[5]=2），其實這個2表示t[5]==『d』的前面有2個字元和開始的兩個字元相同，且t[5]==『d』不等於開始的兩個字元之後的第三個字元（t[2]=『c』）.如圖：
也就是說，如果開始的兩個字元之後的第三個字元也為『d』,那麼，儘管t[5]==『d』的前面有2個字元和開始的兩個字元相同，t[5]==『d』的模式函式值也不為2，而是為0。
s[4] ==t[4]，s[3] ==t[3]，根據next[5]=2，有t[3]==t[0]，t[4] ==t[1]，所以s[3]==t[0]，s[4] ==t[1]（兩對相當於間接比較過了），因此，接下來比較s[5]和t[2]是否相等。
乙個極端的例子是：
在s=「aaaaa…aab「(100個a)中查詢t=」aaaaaaaaab」,簡單匹配演算法每次都是比較到t的結尾，發現字元不同，然後t的下標回溯到開始，s的下標也要回溯相同長度後增1，繼續比較。如果使用kmp匹配演算法，就不必回溯.
對於一般文稿中串的匹配，簡單匹配演算法的時間複雜度可降為o (m+n)，因此在多數的實際應用場合下被應用。
（1）next[0]= -1意義：任何串的第乙個字元的模式值規定為-1。
（2）next[j]= -1意義：模式串t中下標為j的字元，如果與首字元
相同，且j的前面的1—k個字元與開頭的1—k
個字元不等（或者相等但t[k]==t[j]）
（1≤k 如：t=」abcabcad」則next[6]=-1，
因t[3]=t[6]
（3）next[j]=k意義：模式串t中下標為j的字元，如果j的前面k個字元與開頭的k個字元相等，
且t[j] != t[k]（1≤k 即t[0]t[1]t[2]…t[k-1t[j-k]t[j-k+1]t[j-k+2]…t[j-1]
且t[j]!= t[k].（1≤k(4)next[j]=0 意義：除（1）（2）（3）的其他情況。
1）求t=「abcac」的模式函式的值。
next[0]= -1根據(1)
next[1]=0根據(4)因(3)有1<=k next[2]=0根據(4)因(3)有1<=k next[3]= -1根據(2)
next[4]=1根據(3) t[0]=t[3]且t[1]=t[4]
如下圖：
若t=「abcab」將是這樣：
2）求t=」ababcaabc」的模式函式的值。
next[0]= -1根據(1)
next[1]=0根據(4)
next[2]=-1根據(2)
next[3]=0 根據(3)雖然t[0]=t[2]但t[1]=t[3]被劃入(4)
next[4]=2 根據(3) t[0]t[1]=t[2]t[3]且t[2] !=t[4]
next[5]=-1 根據(2)
next[6]=1 根據(3) t[0]=t[5]且t[1]!=t[6]
next[7]=0 根據(3)雖然t[0]=t[6]但t[1]=t[7]被劃入（4）
next[8]=2 根據(3) t[0]t[1]=t[6]t[7]且t[2]!=t[8]
如下圖：
設在字串s中查詢模式串t，若s[m]!=t[n],那麼，取t[n]的模式函式值next[n]。
-1表示s[m]和t[0]間接比較過了，不相等，下一次比較s[m+1]和t[0]
表示比較過程中產生了不相等，下一次比較s[m]和t[0]。
k>0但k4.其他值，不可能。
方法一：
void get_nextval(const char *t, int next)
else
k = next[k];
}}方法二：
void getnext(const char* pattern,int next)
{ next[0]= -1;
int k=-1,j=0;
while(pattern[j] != '/0'){
貪吃蛇設計報告
摘要貪吃蛇遊戲作為一款簡單遊戲，是手機遊戲的代表，在十多年前風靡全世界，時至今日，貪吃蛇遊戲任然活躍的網路的各個角落。本次編寫的便是一款經典的貪吃蛇遊戲，任務確定為實現貪吃蛇遊戲過程。作為遊戲的組成，通過必要的圖形，文字介面來引導遊戲者參與到這款遊戲中，更有效的吸引遊戲者的興趣，為了拓展遊戲者對高分...
C語言課程設計報告
課程名稱計算機高階語言課程設計 c 教師姓名 本科生姓名 本科生學號 本科生專業機械設計製造及其自動化 所在院系機電學院 類別c.本科生 日期2013.7.11 注 1 無評閱人簽名成績無效 2 必須用鋼筆或原子筆批閱，用鉛筆閱卷無效 3 如有平時成績，必須在上面評分表中標出，並計算入總成績。模擬手...
C語言課程設計報告
1.本頁為設計報告要求頁，製作好報告後輸出時將本頁刪除 2.本模板的各種字型及頁面設定請同學們 3.本設計報告左側裝訂。在虛線處裝訂。4.在課程設計封皮一頁上用已經設定好的宋體四號來填寫各個專案。5.在課程設計評定表一頁上用宋體小四填寫班級 學號 姓名 專案組 專案組長 專案組組員 本人工作簡介。組...