當(dāng)前位置：首頁 > 科技 > 軟件

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

來源：責(zé)編：時(shí)間：2024-07-03 17:18:53 1111觀看

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

大家好，我是小風(fēng)哥，今天簡(jiǎn)單聊聊字符串匹配kmp算法。

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

圖片

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

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

圖片

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

圖片

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

圖片

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

圖片

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

圖片

此時(shí)B和A又不同，重復(fù)上述過程。

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

圖片

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

圖片

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

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

圖片

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

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

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

圖片

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

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

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

圖片

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

圖片

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

圖片

只有這么兩種可能。

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

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

圖片

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

圖片

這意味著AB是這個(gè)字符串的后綴：

圖片

AB是這個(gè)字符串的前綴：

圖片

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

圖片

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

圖片

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

圖片

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

圖片

我們直接從子串起始位置進(jìn)行匹配。

圖片

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

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

因此我們來到了第二個(gè)核心問題。

我們以ABCDAB為例來講解。

這是長(zhǎng)度為1的前后綴，這是長(zhǎng)度為2的前后綴，以此類推。

圖片

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

圖片

我們記下來。

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

對(duì)于ABCDA這個(gè)子串來說，相同前后綴長(zhǎng)度是1，因?yàn)閮蓚€(gè)A是相同前后綴。

圖片

而對(duì)于ABCD這個(gè)子串來說，相同前后綴的長(zhǎng)度是0，也就是沒有相同的前后綴。

其它也一樣。

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

圖片

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

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

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

圖片

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

圖片

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

圖片

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

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

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

圖片

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

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

圖片

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

圖片

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

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

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

圖片

因此我們只能找一個(gè)更短的。

圖片

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

圖片

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

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

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

圖片

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

圖片

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

圖片

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

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

圖片

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

也就是這個(gè)位置。

圖片

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

圖片

現(xiàn)在我們?cè)賮砜匆槐檎麄€(gè)過程。

此時(shí)兩個(gè)字符的長(zhǎng)度不等，那么我們只需要簡(jiǎn)單查一下next[n-1]：

圖片

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

圖片

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

圖片

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

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

圖片

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

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

圖片

好啦，以上就是本期全部?jī)?nèi)容。

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

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

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

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

標(biāo)簽：

熱門焦點(diǎn)

帥氣純真少年！日本最帥初中生選美冠軍出爐

日本第一帥哥初一生選美大賽冠軍現(xiàn)已正式出爐，冠軍是來自千葉縣的宗田悠良。日本一直熱衷于各種選美大賽，從“最美JK”起到“最美女星&r
JavaScript 混淆及反混淆代碼工具

介紹在我們開始學(xué)習(xí)反混淆之前，我們首先要了解一下代碼混淆。如果不了解代碼是如何混淆的，我們可能無法成功對(duì)代碼進(jìn)行反混淆，尤其是使用自定義混淆器對(duì)其進(jìn)行混淆時(shí)。什么是混
一篇聊聊Go錯(cuò)誤封裝機(jī)制

%w 是用于錯(cuò)誤包裝（Error Wrapping）的格式化動(dòng)詞。它是用于 fmt.Errorf 和 fmt.Sprintf 函數(shù)中的一個(gè)特殊格式化動(dòng)詞，用于將一個(gè)錯(cuò)誤（或其他可打印的值）包裝在一個(gè)新的錯(cuò)誤中。使
當(dāng)家的盒馬，加速謀生

來源 | 價(jià)值星球Planet作者 | 歸去來自己“當(dāng)家”的盒馬，開始加速謀生了。據(jù)盒馬官微消息，盒馬計(jì)劃今年開放生鮮供應(yīng)鏈，將其生鮮商品送往食堂。目前，盒馬在上海已經(jīng)與
華為將推出盤古數(shù)字人大模型可幫助用戶12小時(shí)完成數(shù)字人生成

在今日舉行的2023年華為云數(shù)字文娛AI創(chuàng)新峰會(huì)上，華為云全球Marketing與銷售服務(wù)總裁石冀琳表示，華為云將在后續(xù)推出盤古數(shù)字人大模型，可幫助用戶12小
國(guó)行版三星Galaxy Z Fold5/Z Flip5發(fā)布售價(jià)7499元起

2023年8月3日，三星電子舉行Galaxy新品中國(guó)發(fā)布會(huì)，正式在國(guó)內(nèi)推出了新一代折疊屏智能手機(jī)三星Galaxy Z Fold5與Galaxy Z Flip5，以及三星Galaxy Tab S9
三星電子Q2營(yíng)收60萬億韓元存儲(chǔ)業(yè)務(wù)營(yíng)收同比仍下滑超過50%

7月27日消息，據(jù)外媒報(bào)道，從三星電子所發(fā)布的財(cái)報(bào)來看，他們主要利潤(rùn)來源的存儲(chǔ)芯片業(yè)務(wù)在今年二季度仍不樂觀，營(yíng)收同比仍在大幅下滑，所在的設(shè)備解決方案
iQOO 11S新品發(fā)布會(huì)

iQOO將在7月4日19:00舉行新品發(fā)布會(huì)，推出杭州亞運(yùn)會(huì)電競(jìng)賽事官方用機(jī)iQOO 11S。
“買真退假” 這種“羊毛”不能薅

□ 法治日?qǐng)?bào) 記者王春　　□ 本報(bào)通訊員胡佳麗　　2020年初，還在上大學(xué)的小東加入了一個(gè)大學(xué)生兼職QQ群。群主“七王”在群里介紹一些刷單賺

AVt天堂网手机版,亚洲va久久久噜噜噜久久4399,天天综合亚洲色在线精品,亚洲一级Av无码毛片久久精品

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

帥氣純真少年！日本最帥初中生選美冠軍出爐

JavaScript 混淆及反混淆代碼工具

一篇聊聊Go錯(cuò)誤封裝機(jī)制

當(dāng)家的盒馬，加速謀生

華為將推出盤古數(shù)字人大模型可幫助用戶12小時(shí)完成數(shù)字人生成

國(guó)行版三星Galaxy Z Fold5/Z Flip5發(fā)布售價(jià)7499元起

三星電子Q2營(yíng)收60萬億韓元存儲(chǔ)業(yè)務(wù)營(yíng)收同比仍下滑超過50%

iQOO 11S新品發(fā)布會(huì)

“買真退假” 這種“羊毛”不能薅

最新推薦

猜你喜歡

熱門推薦

相關(guān)資訊