|
1.概述.
快速模式匹配算法，簡稱 KMP 算法，是在 BF 算法基礎(chǔ)上改進得到的算法。 BF 算的實現(xiàn)過程就是 "傻瓜式" 地用模式串（假定為子串的串）與主串中的字符一一匹配，算法執(zhí)行效率不高，所以為了減少算法的時間復雜度，特引出KMP算法
2.基本原理
example:
7]7VWSX@O}8Z069B_QEYA{L.png (39.37 KB, 下載次數(shù): 83)
下載附件
2020-4-23 14:07 上傳
由此可以看出，每次匹配失敗后模式串移動的距離不一定是 1，某些情況下一次可移動多個位置，這就是 KMP 模式匹配算法
模式串移動距離的判斷：
每次模式匹配失敗后，計算模式串向后移動的距離是 KMP 算法中的核心部分。
其實，匹配失敗后模式串移動的距離和主串沒有關(guān)系，只與模式串本身有關(guān)系。
給每個模式串配備一個數(shù)組（例如 next[]），用于存儲模式串中每個字符對應指針 j 重定向的位置（也就是存儲模式串的數(shù)組下標），比如 j=4，則該字符匹配失敗后指針 j 指向模式串中第4 個字符
3.實現(xiàn) next 數(shù)組的 C 語言代碼：
2.png (55.92 KB, 下載次數(shù): 97)
下載附件
2020-4-23 14:24 上傳
4.next 數(shù)組的缺陷及改進
3.gif (8.13 KB, 下載次數(shù): 83)
下載附件
2020-4-23 14:26 上傳
當匹配失敗時，Next 函數(shù) 開始繼續(xù)進行模式匹配，但是從圖中可以看到，這樣做是沒有必要的，純屬浪費時間
出現(xiàn)這種多余的操作，問題在當 T[i-1]==T[j-1] 成立時，沒有繼續(xù)對 i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判斷。改進后的 Next 函數(shù)如下所示：
4.png (38.28 KB, 下載次數(shù): 99)
下載附件
2020-4-23 14:27 上傳
5.KMP的實現(xiàn)：附件
cKMP算法.rar
(1.18 KB, 下載次數(shù): 12)
2020-4-23 14:30 上傳
點擊文件名下載附件
下載積分: 黑幣 -5
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
