當前位置：首頁 > 科技 > 軟件

徹底理解字符串匹配KMP算法

來源：責編：時間：2024-07-03 17:18:53 1131觀看

導讀大家好，我是小風哥，今天簡單聊聊字符串匹配kmp算法。字符串匹配是計算機科學中非常基礎(chǔ)的操作，給定兩個字符串a(chǎn)和b，我們需要判斷字符串a(chǎn)是否包含字符串b。圖片像你我這樣的普通程序員能想到的最簡單方法是這樣的，用字符串b

大家好，我是小風哥，今天簡單聊聊字符串匹配kmp算法。

字符串匹配是計算機科學中非常基礎(chǔ)的操作，給定兩個字符串a(chǎn)和b，我們需要判斷字符串a(chǎn)是否包含字符串b。

圖片

像你我這樣的普通程序員能想到的最簡單方法是這樣的，用字符串b不斷去匹配每個主串中的子串。

假設(shè)給定這樣兩個字符串：

圖片

首先從主串的第一個位置和子串的第一個位置去匹配，我們發(fā)現(xiàn)A和B不相同：

圖片

因此主串指針后移一位，子串重新從最第一個字符開始匹配。

圖片

這時我們發(fā)現(xiàn)A和C不同，因此匹配失敗。

圖片

主串指針回退到第三個字符，子串重新從第一個字符開始匹配。

圖片

此時B和A又不同，重復上述過程。

這次成功找到多個相同的字符，但最后一個字符匹配失敗：

圖片

按照我們的算法，主串指針需要回退到第5個字符重新匹配。

圖片

這就是你我這種肉體凡胎能想到的算法，時間復雜度是O(mn)，效率低下的原因當然是主串指針需要回退。

然而有三位大神不是這么想的，它們跳出來凡人的思考方式發(fā)明了一種極具創(chuàng)意的算法，由于是三個人同時發(fā)現(xiàn)，因此這個算法取了三人名字的首字母，這就是著名的kmp算法。

圖片

看到這里相信你就能明白為什么這個算法很難掌握了吧，難是正常的，覺得不難才不正常，如果你能無師自通搞定kmp算法，那么早出生幾十年你也能和大師們并駕齊驅(qū)供我等凡夫俗子瞻仰。

廢話不多說，接下來就讓我們領(lǐng)略一下大師的非凡境界。

注意看這個主串指針，大師們思考的第一個問題就是，主串指針是否有必要回退，這是最關(guān)鍵最核心的問題。

圖片

讓我們回到剛才部分匹配的示例。

主串指針是否需要需要回退呢？我們思考兩種可能。

第一種可能，即使能匹配成功，匹配成功的起始位置也在主串指針H及以后，在這種情況下主串指針不需要回退。

圖片

第二種可能，匹配成功的起始位置經(jīng)過主串指針H：

圖片

在這種情況下，主串指針之前的兩個字符A和B一定是成功匹配了的：此時我們只需要比較主串指針H及以后的位置即可。

圖片

只有這么兩種可能。

因此可以看到，主串指針根本就沒有必要回退。

現(xiàn)在我們知道了主串指針不需要回退，那么子串指針該從哪里開始匹配呢？從頭開始嗎？

圖片

注意看我們剛才提到的第二種可能，匹配成功的起始位置經(jīng)過主串指針H，在這種情況下，主串指針之前的兩個字符A和B一定是成功匹配了的，這意味著什么呢？

圖片

這意味著AB是這個字符串的后綴：

圖片

AB是這個字符串的前綴：

圖片

不要忘了這兩個字符串是成功匹配了的：

圖片

也就是說這是兩個完全相同的字符串，這就意味著AB是成功匹配字符串的相同前后綴。

圖片

這樣子符串指針也不需要回退到起始位置，而是從共同前后綴的下一個位置開始匹配即可。

圖片

而對于部分匹配的子串根本不存在共同前后綴的情況，

圖片

我們直接從子串起始位置進行匹配。

圖片

可以看到，由于主串指針不回退，這大幅提高了算法的效率。

想要實現(xiàn)這樣的算法，關(guān)鍵是怎樣計算出部分匹配子串的共同前后綴。

因此我們來到了第二個核心問題。

我們以ABCDAB為例來講解。

這是長度為1的前后綴，這是長度為2的前后綴，以此類推。

圖片

可以看到，在所有的前后綴中，相同前后綴的最大長度是2。

圖片

我們記下來。

實際上我們需要把所有子串的相同前后綴都計算出來。

對于ABCDA這個子串來說，相同前后綴長度是1，因為兩個A是相同前后綴。

圖片

而對于ABCD這個子串來說，相同前后綴的長度是0，也就是沒有相同的前后綴。

其它也一樣。

這樣我們就到了一個數(shù)組，通過查找這個數(shù)組我們能知道任意子串的共同前后綴長度。

圖片

這個數(shù)組在很多資料中被稱之為next數(shù)組。

有了next數(shù)組就簡單了。

假設(shè)此時我們發(fā)現(xiàn)兩個指針指向的字符不同，接下來只需要簡單查找next數(shù)組：

圖片

發(fā)現(xiàn)已匹配部分的相同前后綴長度是2：

圖片

因此主指針不動，子串指針移動到相同前后綴的下一個位置繼續(xù)去匹配即可。

圖片

可以看到，只要我們能得到next數(shù)組，就可以在線性時間復雜度內(nèi)解決問題。

這里，我們來到了第三個核心問題，那就是該怎樣高效計算出next數(shù)組。

假設(shè)此時我們已經(jīng)計算出了這個子串的共同前后綴，也就是長度為n的這兩個部分。

圖片

接下來計算下一個位置的最長前后綴，我們只需要分別后移兩個指針，然后比較字符是否相等，這里有兩種可能。

第一種可能是接下來的字符相同，那么這個子串的最長相同前后綴的長度就是n+1。

圖片

然后寫到next數(shù)組即可，這很好理解。

圖片

但是如果下一個位置的字符不相等該怎么辦呢？

注意接下來是整個算法最核心的，也是最具技巧的地方。

如果接下來的兩個字符不相等，那么前面的這部分絕無可能形成最長前后綴。

圖片

因此我們只能找一個更短的。

圖片

如果能找到一個更短的，這就意味著這兩部分會形成一個共同前后綴。

圖片

然后我們繼續(xù)比較下一個字符就可以了，這就回到最初的問題。

那么這兩部分相同意味著什么呢？

不要忘了紅色部分是我們之前找到一個共同前后綴，也就是說紅色部分的子串完全相同。

圖片

而現(xiàn)在這兩個子串也相同，這就意味著這兩個更小的子串其實是紅色部分子串的最長前后綴。

圖片

不要忘了，此時我們的指針已經(jīng)來到了這里，前面這部分的next數(shù)組已經(jīng)計算出來了。

圖片

通過查next數(shù)組，我們可以快速得到更短前后綴的長度。

既然紅色部分的長度是n，那么更短前后綴的長度其實就是next[n-1]。

圖片

再來看下，紅色部分的長度是n，那么更短前后綴的長度是next[n-1]。

也就是這個位置。

圖片

這就是計算next數(shù)組源代碼中n=next[n-1]這句話的含義。

圖片

現(xiàn)在我們再來看一遍整個過程。

此時兩個字符的長度不等，那么我們只需要簡單查一下next[n-1]：

圖片

這就是更短的前后綴長度，假設(shè)是4。

圖片

此時前一個指針回退到位置4，繼續(xù)比較下一個字符即可。

圖片

如果下一個字符相同，那么當前位置next數(shù)組的值就是n+1。

而如果下一個字符不相同，我們繼續(xù)查找next[n-1]，然后前一個指針回退，繼續(xù)比較下一個位置即可。

圖片

這就是完整的kmp算法實現(xiàn)，可以看到整個代碼實際上只有30多行。

如果你能在50多年前寫出這幾行代碼，你也能和它們并列，在計算機科學史上會留下你的一筆。

圖片

好啦，以上就是本期全部內(nèi)容。

本文鏈接：http://www.www897cc.com/showinfo-26-98552-0.html徹底理解字符串匹配KMP算法

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： Python 串口收發(fā)使用與示例教程

下一篇： XLSX插件全面解析：從入門到精通的數(shù)據(jù)處理神器

標簽：

熱門焦點

iPhone賣不動了！蘋果股價創(chuàng)年內(nèi)最大日跌幅：市值一夜蒸發(fā)萬億元

8月5日消息，今天凌晨美股三大指數(shù)高開低走集體收跌，道指跌0.41%；納指跌0.36%；標普500指數(shù)跌0.52%。熱門科技股也都變化極大，其中蘋果報181.99美元，跌4.8%，創(chuàng)
三言兩語說透設(shè)計模式的藝術(shù)-簡單工廠模式

一、寫在前面工廠模式是最常見的一種創(chuàng)建型設(shè)計模式，通常說的工廠模式指的是工廠方法模式，是使用頻率最高的工廠模式。簡單工廠模式又稱為靜態(tài)工廠方法模式，不屬于GoF 23種設(shè)計
服務(wù)存儲設(shè)計模式：Cache-Aside模式

Cache-Aside模式一種常用的緩存方式，通常是把數(shù)據(jù)從主存儲加載到KV緩存中，加速后續(xù)的訪問。在存在重復度的場景，Cache-Aside可以提升服務(wù)性能，降低底層存儲的壓力，缺點是緩存和底
使用Webdriver-manager解決瀏覽器與驅(qū)動不匹配所帶來自動化無法執(zhí)行的問題

1、前言在我們使用 Selenium 進行 UI 自動化測試時，常常會因為瀏覽器驅(qū)動與瀏覽器版本不匹配，而導致自動化測試無法執(zhí)行，需要手動去下載對應(yīng)的驅(qū)動版本，并替換原有的驅(qū)動，可能還
微博大門常打開，迎接海外畫師漂洋東渡

作者:互聯(lián)網(wǎng)那些事“起猛了，我能看得懂日語了”。“為什么日本人說話我能聽懂？”“中文不像中文，日語不像日語，但是我竟然看懂了”…&hell
AMD的AI芯片轉(zhuǎn)單給三星可能性不大與臺積電已合作至2nm制程

據(jù) DIGITIMES 消息，英偉達 AI GPU 出貨逐季飆升，接下來 AMD MI 300 系列將在第 4 季底量產(chǎn)。而半導體業(yè)內(nèi)人士表示，近日傳出 AMD 的 AI 芯片將轉(zhuǎn)單給
三星顯示已開始為AR設(shè)備研發(fā)硅基LED微顯示屏

7月18日消息，據(jù)外媒報道，隨著蘋果首款頭顯產(chǎn)品Vision Pro在6月份正式推出，AR/VR/MR等頭顯產(chǎn)品也就將成為各大公司下一個重要的競爭領(lǐng)域，對顯示屏這一關(guān)
iQOO Neo8 Pro即將開售：到手價3099元起安卓性能最強旗艦

5月23日，iQOO如期舉行了新品發(fā)布會，全新的iQOO Neo8系列也正式與大家見面，包含iQOO Neo8和iQOO Neo8 Pro兩個版本，其中標準版搭載高通驍龍8+，而Pro版更
上海舉辦人工智能大會活動，建設(shè)人工智能新高地

人工智能大會在上海浦江兩岸隆重拉開帷幕，人工智能新技術(shù)、新產(chǎn)品、新應(yīng)用、新理念集中亮相。8月30日晚，作為大會的特色活動之一的上海人工智能發(fā)展盛典人工

日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

徹底理解字符串匹配KMP算法

iPhone賣不動了！蘋果股價創(chuàng)年內(nèi)最大日跌幅：市值一夜蒸發(fā)萬億元

三言兩語說透設(shè)計模式的藝術(shù)-簡單工廠模式

服務(wù)存儲設(shè)計模式：Cache-Aside模式

使用Webdriver-manager解決瀏覽器與驅(qū)動不匹配所帶來自動化無法執(zhí)行的問題

微博大門常打開，迎接海外畫師漂洋東渡

AMD的AI芯片轉(zhuǎn)單給三星可能性不大與臺積電已合作至2nm制程

三星顯示已開始為AR設(shè)備研發(fā)硅基LED微顯示屏

iQOO Neo8 Pro即將開售：到手價3099元起安卓性能最強旗艦

上海舉辦人工智能大會活動，建設(shè)人工智能新高地

最新推薦

猜你喜歡

熱門推薦

相關(guān)資訊