国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業(yè)教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 數據結構中KMP算法是什么?

數據結構中KMP算法是什么?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 07:11:44 1696979504

一、數據結構中KMP算法

KMP算法介紹

KMP算法是一種改進的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人們稱它為克努特—莫里斯—普拉特操作(簡稱KMP算法)。KMP算法是在 BF 算法基礎上改進得到的算法。學習 BF 算法我們知道,該算法的實現(xiàn)過程就是 “傻瓜式” 地用模式串(假定為子串的串)與主串中的字符一一匹配,匹配不成功則返回到上一次與主串匹配的下一位字符進行匹配,算法執(zhí)行效率不高。

KMP算法的解決題型

KMP算法是在數據結構中兩個字符串相互匹配衍生出來的算法。KMP算法的作用是在一個已知字符串中查找子串的位置,也叫做串的模式匹配。例如,對主串 A(“ABCABCE”)和模式串 B(“ABCE”)進行模式匹配,如果人為去判斷,僅需匹配兩次。雖然在以上字符較少的串中人為匹配很容易,但是讓計算機來匹配就相對慢一些,但是當字符串中的字符非常多的時候,就不可能人為去匹配。所以打鐵還需自身硬,我們把這種枯燥的事以一定的算法交給計算機處理。

KMP算法相比BF算法的改進

每當一趟匹配過程中出現(xiàn)字符比較不等時,無需回溯i指針(即無需將i指針完全退回至i-j+1),而是利用已經得到的“部分匹配”的結果將模式向右“滑動”盡可能遠的一段距離后,繼續(xù)進行比較。

需要解決的問題:當主串中的第i個字符與模式中第j個字符比較不相等時,主串中第i個字符(i指針不回溯)應與模式中哪個字符再比較?—-假設從主串中第i個字符與模式中的第k個字符再進行比較

它是則呢樣來消除回溯的呢?就是因為它提取并運用了加速匹配的信息!

  這種信息就是對于每模式串 t 的每個元素 t j,都存在一個實數 k ,使得模式串 t 開頭的 k 個字符(t 0 t 1…t k-1)依次與 t j 前面的 k(t j-k t j-k+1…t j-1,這里名列前茅個字符 t j-k 非常多從 t 1 開始,所以 k < j)個字符相同。如果這樣的 k 有多個,則取最大的一個。模式串 t 中每個位置 j 的字符都有這種信息,采用 next 數組表示,即 next[ j ]=MAX{ k }。

延伸閱讀:

二、KMP算法的時間復雜度

主要由兩部分組成:預處理部分和匹配部分。

預處理部分:在這一步,算法計算模式串的最長公共前綴和后綴(也稱為部分匹配表或失效函數)。這一步的時間復雜度為O(m),因為它遍歷了整個模式串。匹配部分:在這一步,算法在目標文本中查找模式串。在最壞的情況下,這一步的時間復雜度為O(n)。這是因為算法在進行比較時,可以根據失效函數跳過不匹配的字符,因此,它不需要對每個字符進行逐一比較。

綜合考慮這兩部分,KMP算法的總時間復雜度為O(m+n)。與樸素的字符串匹配算法相比(其時間復雜度為O(mn)),KMP算法具有更高的效率,尤其在處理大量數據時。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業(yè)內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT