九分鐘帶你弄懂KMP算法【原理篇】-創(chuàng)新互聯(lián)

前言：

創(chuàng)新互聯(lián)是一家專注于網(wǎng)站制作、做網(wǎng)站與策劃設(shè)計,覃塘網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:覃塘等地區(qū)。覃塘做網(wǎng)站價格咨詢:18980820575

在一些尋找子串的問題中，我們常常使用的是BF算法，也就是暴力算法，這樣做的時間復(fù)雜度通常都是O(N^2)，且不能體現(xiàn)出算法的美妙之處（虐人之處），于是三位大佬D.E.Knuth，J.H.Morris和V.R.Pratt提出了一種船新的方法，時間復(fù)雜度真的很低 O(n+m),這個算法由三位大牛的名字首字母來命名，也就是我們今天的主角KMP算法。

? 我將KMP算法的詳解分為三個篇章：

->【原理篇】：主要講解KMP實現(xiàn)的原理，以及手動求NEXT數(shù)組。

【數(shù)理篇】：主要講解如何在手動求出NEXT數(shù)組的情況下，找出數(shù)學(xué)規(guī)律，為之后的算法實現(xiàn)奠定基礎(chǔ)。

【實現(xiàn)篇】：主要講解以C語言代碼的方式實現(xiàn)KMP算法，以及NEXT數(shù)組的優(yōu)化。

其余篇章將在之后更新

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈

制作不易，若對你有幫助的話點贊、關(guān)注、評論走一波，你們的支持是我前進路上大的動力。

實現(xiàn)原理：?

? 當(dāng)你有兩個字符串DES（目標(biāo)字符串）和PAT（模板字符串），你要去DES中尋找是否有子字符串與模板串PAT相同。

? BF也就是暴力算法的實現(xiàn)思路是這樣的：當(dāng)DES[i]==PAT[j]的時候，先記錄此時的I下標(biāo)，令cnt=I,之后執(zhí)行I++，J++。若DES[i]!=PAT[j]的時候I回退到起始下標(biāo)，也就是cnt的位置，j回退到PAT字符串的首位也就A(0)的位置；

聰明的你一定發(fā)現(xiàn)，這樣做會導(dǎo)致i和j一直往回走，效率實在不高，有沒有可能讓j有規(guī)律的回退，而i一直向前呢？

KMP算法就是這樣做的！

試想一下，當(dāng)i與j分別指向這的時候，表示前三個字符都匹配上了，接下來我們按照BF算法的思路，讓i，j向后移動一格。

這時候DES[i]所指向的字符為A，而PAT[j]所指向的字符為C，按照BF的思路，此時i j都需要執(zhí)行一個回退的操作。但你們仔細觀察看看，j能指向C是否能說明，前三個元素AAA是DES中前四個元素的一個子串？

也就是說PAT的AAA一定在DES中能被匹配上，不然J也無法移動到這了。

那我們這時候還需要將J回退到最開始的位置嗎？我們不需要了！我們只需要將j移動到PAT數(shù)組中，以PAT[0]為首，PAT[j-1]為結(jié)尾的兩個子字符串的長度位就可以了。聽不懂沒關(guān)系，底下我會介紹這種算法

（例如AAA，以第一個A為首，中間的A為尾是第一個子字符串，以中間的A為首，最后一個A為尾是第二個子字符串，這兩個子字符串的長度為2，2為長度位，這時將J移動到PAT中下標(biāo)為2的地方）。

但你不禁會想：為什么要這么退呢？因為你退回的是DES中匹配過的所有的字符的子字符串。這是一個難點，可以自己多舉幾個例子想想。若沒聽懂也可以先接著往下看，影響不大。

這也就是KMP算法當(dāng)中的核心之處：NEXT數(shù)組。

NEXT數(shù)組：

在前面，我們已經(jīng)簡單體會到了NEXT數(shù)組，可以用這么一句話來概括NEXT數(shù)組的作用

指導(dǎo)PAT中的j要回退到PAT中的哪一個位置。NEXT[j]存儲了從PAT[0]到PAT[j-1]位置，以PAT[0]為首，PAT[j-1]為結(jié)尾的兩個最長子字符串的長度位（可以重疊，但不能相等）。

那么我們怎么來求NEXT數(shù)組呢？別急，接下來我會舉兩個例子。

EX1：

012345678910
PAT字符串abcababcabc
NEXT數(shù)組-10001212345

我們規(guī)定，NEXT[0]=-1 NEXT[1]=0.(有些地方的定義不一樣，但這沒關(guān)系，在代碼中做相應(yīng)修改就可以了)從NEXT[2]開始，我們需要自己算。

牢記我們的口訣，NEXT[j]=以PAT[0]為首，PAT[j-1]為結(jié)尾的兩個最長子字符串的長度位（可以重疊，但不能相等）。

我們看看NEXT[2]中是否滿足呢，首：a 尾：b顯然沒有以a為首b為尾的字符串，那么我們就在這里填上0，也就是NEXT[2]=0；

NEXT[3]：首：a? 尾：c，顯然也沒有以a為首，c為尾的兩個子字符串，所以NEXT[3]=0;

NEXT[4]：首：a? 尾：a，pat[0]=a,pat[3]=a，找到了兩個子字符串（就是首尾本身），他們有多長呢？顯然是長度1，所以NEXT[4]=1；

NEXT[5]：首：a? 尾：b，pat[0-1]=ab,pat[3-4]=ab（這里表示下標(biāo)3到下標(biāo)4，下同），找到了兩個子字符串，以PAT[0]為首，PAT[4（5-1）]為尾的兩個字符串，長度為2，所以NEXT[5]=2；

NEXT[6]：首：a? 尾：a，pat[0]=a,pat[5]=a，找到了兩個字符串（就是首尾本身），他們有多長呢？顯然是長度1，所以NEXT[6]=1；

NEXT[7]：首：a? 尾：b，pat[0-1]=ab,pat[5-6]=ab，找到了兩個子字符串，以PAT[0]為首，PAT[6（7-1）]為尾的兩個字符串，長度為2，所以NEXT[7]=2；

NEXT[8]：首：a? 尾：c，pat[0-2]=abc,pat[5-7]=abc，找到了兩個子字符串，以PAT[0]為首，PAT[7（8-1）]為尾的兩個字符串，長度為3，所以NEXT[8]=3；

NEXT[9]：首：a? 尾：a，pat[0-3]=abca,pat[5-8]=abca，找到了兩個子字符串，以PAT[0]為首，PAT[8（9-1）]為尾的兩個字符串，長度為4，所以NEXT[9]=4；

NEXT[10]：首：a? 尾：b，pat[0-4]=abcab,pat[5-9]=abcab，找到了兩個子字符串，以PAT[0]為首，PAT[9（10-1）]為尾的兩個字符串，長度為5，所以NEXT[10]=5；

到此，該PAT的next數(shù)組已經(jīng)告一段落。下面還有一個例子，我直接給出了答案，若還是沒懂，可以對照上面的方法進行求解或評論私信問我都可。

012345678910
PAT數(shù)組abcababcabc
NEXT數(shù)組-10001212345

至此，本篇博客的內(nèi)容九分鐘帶你弄懂KMP算法【原理篇】告一段落，若對你有些許幫助，可以點贊、關(guān)注、評論支持下博主，你的支持將是我前進路上大的動力。

若以上內(nèi)容有任何問題，歡迎在評論區(qū)指出。若對以上內(nèi)容有任何不解，都可私信評論詢問。

諸君，山頂見！

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：九分鐘帶你弄懂KMP算法【原理篇】-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://muchs.cn/article34/dhgpse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、軟件開發(fā)、品牌網(wǎng)站制作、云服務(wù)器、企業(yè)網(wǎng)站制作、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站