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

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁  >  技術(shù)干貨  > 數(shù)據(jù)結(jié)構(gòu)中KMP算法是什么?

數(shù)據(jù)結(jié)構(gòu)中KMP算法是什么?

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

一、數(shù)據(jù)結(jié)構(gòu)中KMP算法

KMP算法介紹

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

KMP算法的解決題型

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

KMP算法相比BF算法的改進(jìn)

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

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

它是則呢樣來消除回溯的呢?就是因?yàn)樗崛〔⑦\(yùn)用了加速匹配的信息!

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

延伸閱讀:

二、KMP算法的時(shí)間復(fù)雜度

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

預(yù)處理部分:在這一步,算法計(jì)算模式串的最長(zhǎng)公共前綴和后綴(也稱為部分匹配表或失效函數(shù))。這一步的時(shí)間復(fù)雜度為O(m),因?yàn)樗闅v了整個(gè)模式串。匹配部分:在這一步,算法在目標(biāo)文本中查找模式串。在最壞的情況下,這一步的時(shí)間復(fù)雜度為O(n)。這是因?yàn)樗惴ㄔ谶M(jìn)行比較時(shí),可以根據(jù)失效函數(shù)跳過不匹配的字符,因此,它不需要對(duì)每個(gè)字符進(jìn)行逐一比較。

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

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請(qǐng)您保持通訊暢通,專屬學(xué)習(xí)老師24小時(shí)內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
軟件架構(gòu)如何能夠滿足ASPICE流程?

一、軟件架構(gòu)如何能夠滿足ASPICE流程架構(gòu)的用途是把整個(gè)產(chǎn)品劃分為更為細(xì)節(jié)的板塊:軟件、硬件、通信等。在這個(gè)基礎(chǔ)上軟件整體將按照用途、功能...詳情>>

2023-10-11 08:47:00
紅黑樹為什么叫紅黑樹?

一、紅黑樹叫紅黑樹的原因紅黑樹(Red-Black Tree)是一種自平衡的二叉搜索樹(Binary Search Tree),其在插入和刪除操作時(shí)能夠自動(dòng)調(diào)整樹的結(jié)...詳情>>

2023-10-11 08:42:41
為什么數(shù)組索引數(shù)據(jù)那么快速、有效?

一、數(shù)組索引數(shù)據(jù)快速、有效的原因1、連續(xù)內(nèi)存存儲(chǔ)數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的,數(shù)組的元素在內(nèi)存中按照一定的順序排列,相鄰元素之間沒有間隔。...詳情>>

2023-10-11 08:36:19
數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹是什么?

一、數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹逐點(diǎn)插入法三角剖分是一種研究方法。三角剖分≠TIN三角剖分是代數(shù)拓?fù)鋵W(xué)里最基本的研究方法。 以曲面為...詳情>>

2023-10-11 08:08:01
在數(shù)據(jù)結(jié)構(gòu)中i=L->length是什么意思?

一、在數(shù)據(jù)結(jié)構(gòu)中i=L->length是什么意思在數(shù)據(jù)結(jié)構(gòu)中,i=L->length通常表示一個(gè)線性表L的長(zhǎng)度,即L中元素的個(gè)數(shù)。線性表是一種數(shù)據(jù)結(jié)構(gòu),它由n...詳情>>

2023-10-11 07:54:48
快速通道