數據結構KMP算法C語言源程序

1.概述.

快速模式匹配算法，簡稱 KMP 算法，是在 BF 算法基礎上改進得到的算法。 BF 算的實現過程就是 "傻瓜式" 地用模式串（假定為子串的串）與主串中的字符一一匹配，算法執行效率不高，所以為了減少算法的時間復雜度，特引出KMP算法

2.基本原理
example:

由此可以看出，每次匹配失敗后模式串移動的距離不一定是 1，某些情況下一次可移動多個位置，這就是 KMP 模式匹配算法

模式串移動距離的判斷：
每次模式匹配失敗后，計算模式串向后移動的距離是 KMP 算法中的核心部分。
其實，

匹配失敗后模式串移動的距離和主串沒有關系，只與模式串本身有關系。

給每個模式串配備一個數組（例如 next[]），用于存儲模式串中每個字符對應指針 j 重定向的位置（也就是存儲模式串的數組下標），比如 j=4，則該字符匹配失敗后指針 j 指向模式串中第4 個字符
3.實現 next 數組的 C 語言代碼：




4.next 數組的缺陷及改進

當匹配失敗時，Next 函數 開始繼續進行模式匹配，但是從圖中可以看到，這樣做是沒有必要的，純屬浪費時間

出現這種多余的操作，問題在當 T[i-1]==T[j-1] 成立時，沒有繼續對 i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判斷。改進后的 Next 函數如下所示：

5.KMP的實現：附件 KMP算法C源碼.rar (1.18 KB, 售價: 1 E幣)

2020-4-25 17:07 上傳

點擊文件名下載附件
售價: 1 E幣  [記錄]  [購買]

【必讀】版權免責聲明

1、本主題所有言論和內容純屬會員個人意見，與本論壇立場無關。2、本站對所發內容真實性、客觀性、可用性不做任何保證也不負任何責任，網友之間僅出于學習目的進行交流。3、對提供的數字內容不擁有任何權利，其版權歸原著者擁有。請勿將該數字內容進行商業交易、轉載等行為，該內容只為學習所提供，使用后發生的一切問題與本站無關。 4、本網站不保證本站提供的下載資源的準確性、安全性和完整性;同時本網站也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的損失或傷害。 5、本網站所有軟件和資料均為網友推薦收集整理而來，僅供學習用途使用，請務必下載后兩小時內刪除，禁止商用。6、如有侵犯你版權的，請及時聯系我們（電子郵箱1370723259@qq.com）指出，本站將立即改正。