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

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

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

來源: 責編: 時間:2024-07-03 17:18:53 1108觀看
導讀大家好,我是小風哥,今天簡單聊聊字符串匹配kmp算法。字符串匹配是計算機科學中非常基礎的操作,給定兩個字符串a和b,我們需要判斷字符串a是否包含字符串b。圖片像你我這樣的普通程序員能想到的最簡單方法是這樣的,用字符串b

大家好,我是小風哥,今天簡單聊聊字符串匹配kmp算法。lf128資訊網——每日最新資訊28at.com

字符串匹配是計算機科學中非常基礎的操作,給定兩個字符串a和b,我們需要判斷字符串a是否包含字符串b。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

像你我這樣的普通程序員能想到的最簡單方法是這樣的,用字符串b不斷去匹配每個主串中的子串。lf128資訊網——每日最新資訊28at.com

假設給定這樣兩個字符串:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

首先從主串的第一個位置和子串的第一個位置去匹配,我們發現A和B不相同:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

因此主串指針后移一位,子串重新從最第一個字符開始匹配。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

這時我們發現A和C不同,因此匹配失敗。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

主串指針回退到第三個字符,子串重新從第一個字符開始匹配。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

此時B和A又不同,重復上述過程。lf128資訊網——每日最新資訊28at.com

這次成功找到多個相同的字符,但最后一個字符匹配失敗:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

按照我們的算法,主串指針需要回退到第5個字符重新匹配。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

這就是你我這種肉體凡胎能想到的算法,時間復雜度是O(mn),效率低下的原因當然是主串指針需要回退。lf128資訊網——每日最新資訊28at.com

然而有三位大神不是這么想的,它們跳出來凡人的思考方式發明了一種極具創意的算法,由于是三個人同時發現,因此這個算法取了三人名字的首字母,這就是著名的kmp算法。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

看到這里相信你就能明白為什么這個算法很難掌握了吧,難是正常的,覺得不難才不正常,如果你能無師自通搞定kmp算法,那么早出生幾十年你也能和大師們并駕齊驅供我等凡夫俗子瞻仰。lf128資訊網——每日最新資訊28at.com

廢話不多說,接下來就讓我們領略一下大師的非凡境界。lf128資訊網——每日最新資訊28at.com

注意看這個主串指針,大師們思考的第一個問題就是,主串指針是否有必要回退,這是最關鍵最核心的問題。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

讓我們回到剛才部分匹配的示例。lf128資訊網——每日最新資訊28at.com

主串指針是否需要需要回退呢?我們思考兩種可能。lf128資訊網——每日最新資訊28at.com

第一種可能,即使能匹配成功,匹配成功的起始位置也在主串指針H及以后,在這種情況下主串指針不需要回退。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

第二種可能,匹配成功的起始位置經過主串指針H:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

在這種情況下,主串指針之前的兩個字符A和B一定是成功匹配了的:此時我們只需要比較主串指針H及以后的位置即可。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

只有這么兩種可能。lf128資訊網——每日最新資訊28at.com

因此可以看到,主串指針根本就沒有必要回退。lf128資訊網——每日最新資訊28at.com

現在我們知道了主串指針不需要回退,那么子串指針該從哪里開始匹配呢?從頭開始嗎?lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

注意看我們剛才提到的第二種可能,匹配成功的起始位置經過主串指針H,在這種情況下,主串指針之前的兩個字符A和B一定是成功匹配了的,這意味著什么呢?lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

這意味著AB是這個字符串的后綴:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

AB是這個字符串的前綴:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

不要忘了這兩個字符串是成功匹配了的:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

也就是說這是兩個完全相同的字符串,這就意味著AB是成功匹配字符串的相同前后綴。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

這樣子符串指針也不需要回退到起始位置,而是從共同前后綴的下一個位置開始匹配即可。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

而對于部分匹配的子串根本不存在共同前后綴的情況,lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

我們直接從子串起始位置進行匹配。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

可以看到,由于主串指針不回退,這大幅提高了算法的效率。lf128資訊網——每日最新資訊28at.com

想要實現這樣的算法,關鍵是怎樣計算出部分匹配子串的共同前后綴。lf128資訊網——每日最新資訊28at.com

因此我們來到了第二個核心問題。lf128資訊網——每日最新資訊28at.com

我們以ABCDAB為例來講解。lf128資訊網——每日最新資訊28at.com

這是長度為1的前后綴,這是長度為2的前后綴,以此類推。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

可以看到,在所有的前后綴中,相同前后綴的最大長度是2。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

我們記下來。lf128資訊網——每日最新資訊28at.com

實際上我們需要把所有子串的相同前后綴都計算出來。lf128資訊網——每日最新資訊28at.com

對于ABCDA這個子串來說,相同前后綴長度是1,因為兩個A是相同前后綴。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

而對于ABCD這個子串來說,相同前后綴的長度是0,也就是沒有相同的前后綴。lf128資訊網——每日最新資訊28at.com

其它也一樣。lf128資訊網——每日最新資訊28at.com

這樣我們就到了一個數組,通過查找這個數組我們能知道任意子串的共同前后綴長度。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

這個數組在很多資料中被稱之為next數組。lf128資訊網——每日最新資訊28at.com

有了next數組就簡單了。lf128資訊網——每日最新資訊28at.com

假設此時我們發現兩個指針指向的字符不同,接下來只需要簡單查找next數組:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

發現已匹配部分的相同前后綴長度是2:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

因此主指針不動,子串指針移動到相同前后綴的下一個位置繼續去匹配即可。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

可以看到,只要我們能得到next數組,就可以在線性時間復雜度內解決問題。lf128資訊網——每日最新資訊28at.com

這里,我們來到了第三個核心問題,那就是該怎樣高效計算出next數組。lf128資訊網——每日最新資訊28at.com

假設此時我們已經計算出了這個子串的共同前后綴,也就是長度為n的這兩個部分。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

接下來計算下一個位置的最長前后綴,我們只需要分別后移兩個指針,然后比較字符是否相等,這里有兩種可能。lf128資訊網——每日最新資訊28at.com

第一種可能是接下來的字符相同,那么這個子串的最長相同前后綴的長度就是n+1。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

然后寫到next數組即可,這很好理解。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

但是如果下一個位置的字符不相等該怎么辦呢?lf128資訊網——每日最新資訊28at.com

注意接下來是整個算法最核心的,也是最具技巧的地方。lf128資訊網——每日最新資訊28at.com

如果接下來的兩個字符不相等,那么前面的這部分絕無可能形成最長前后綴。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

因此我們只能找一個更短的。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

如果能找到一個更短的,這就意味著這兩部分會形成一個共同前后綴。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

然后我們繼續比較下一個字符就可以了,這就回到最初的問題。lf128資訊網——每日最新資訊28at.com

那么這兩部分相同意味著什么呢?lf128資訊網——每日最新資訊28at.com

不要忘了紅色部分是我們之前找到一個共同前后綴,也就是說紅色部分的子串完全相同。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

而現在這兩個子串也相同,這就意味著這兩個更小的子串其實是紅色部分子串的最長前后綴。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

不要忘了,此時我們的指針已經來到了這里,前面這部分的next數組已經計算出來了。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

通過查next數組,我們可以快速得到更短前后綴的長度。lf128資訊網——每日最新資訊28at.com

既然紅色部分的長度是n,那么更短前后綴的長度其實就是next[n-1]。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

再來看下,紅色部分的長度是n,那么更短前后綴的長度是next[n-1]。lf128資訊網——每日最新資訊28at.com

也就是這個位置。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

這就是計算next數組源代碼中n=next[n-1]這句話的含義。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

現在我們再來看一遍整個過程。lf128資訊網——每日最新資訊28at.com

此時兩個字符的長度不等,那么我們只需要簡單查一下next[n-1]:lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

這就是更短的前后綴長度,假設是4。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

此時前一個指針回退到位置4,繼續比較下一個字符即可。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

如果下一個字符相同,那么當前位置next數組的值就是n+1。lf128資訊網——每日最新資訊28at.com

而如果下一個字符不相同,我們繼續查找next[n-1],然后前一個指針回退,繼續比較下一個位置即可。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

這就是完整的kmp算法實現,可以看到整個代碼實際上只有30多行。lf128資訊網——每日最新資訊28at.com

如果你能在50多年前寫出這幾行代碼,你也能和它們并列,在計算機科學史上會留下你的一筆。lf128資訊網——每日最新資訊28at.com

圖片圖片lf128資訊網——每日最新資訊28at.com

lf128資訊網——每日最新資訊28at.com

好啦,以上就是本期全部內容。lf128資訊網——每日最新資訊28at.com

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

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

上一篇: Python 串口收發使用與示例教程

下一篇: XLSX插件全面解析:從入門到精通的數據處理神器

標簽:
  • 熱門焦點
Top 主站蜘蛛池模板: 四会市| 东平县| 名山县| 武威市| 惠来县| 赣榆县| 吉水县| 承德县| 雷波县| 图木舒克市| 礼泉县| 夏津县| 奇台县| 永春县| 石棉县| 开阳县| 成安县| 前郭尔| 迁安市| 长泰县| 丹巴县| 柳江县| 聊城市| 临猗县| 丰镇市| 油尖旺区| 涞水县| 甘泉县| 金阳县| 磐安县| 建平县| 玉门市| 平江县| 珲春市| 基隆市| 伊春市| 得荣县| 玉门市| 宣化县| 临安市| 广东省|