1. 項(xiàng)目概述為什么我們需要KMP算法在字符串匹配這個(gè)老生常談的問題上我們最熟悉的莫過于“暴力匹配”Brute-Force。它的邏輯簡(jiǎn)單直接從主串的第一個(gè)字符開始逐個(gè)與模式串對(duì)齊比較一旦發(fā)現(xiàn)不匹配模式串就往后挪一位從頭再來。這就像你拿著一把鑰匙去試一個(gè)有很多鎖孔的鎖每次從第一個(gè)鎖孔開始試不對(duì)就換下一個(gè)鎖孔從頭試起。在大多數(shù)情況下這沒什么問題但當(dāng)主串和模式串都很長(zhǎng)且部分匹配度很高時(shí)這種方法的效率就顯得捉襟見肘了。想象一下主串是“aaaaaaaaab”模式串是“aaaab”暴力匹配會(huì)在前面一連串的‘a(chǎn)’上反復(fù)進(jìn)行幾乎完全匹配直到最后一個(gè)字符才失敗然后回退、再重復(fù)時(shí)間復(fù)雜度直奔O(m*n)而去。KMP算法Knuth-Morris-Pratt算法正是為了解決這種低效的回退問題而誕生的。它的核心思想是當(dāng)某個(gè)字符匹配失敗時(shí)模式串能夠“智能地”向后滑動(dòng)多位而不是僅僅一位并且利用已經(jīng)匹配成功的那部分信息避免主串指針的回溯。這相當(dāng)于你試鑰匙時(shí)發(fā)現(xiàn)第三個(gè)齒不對(duì)你不是換下一個(gè)鎖孔從頭試而是根據(jù)前兩個(gè)齒已經(jīng)匹配的信息直接跳到某個(gè)可能匹配的鎖孔位置繼續(xù)嘗試。這種“記憶”能力使得KMP算法的時(shí)間復(fù)雜度可以優(yōu)化到O(mn)在處理大規(guī)模文本搜索如編輯器查找、病毒特征碼匹配、DNA序列分析時(shí)優(yōu)勢(shì)巨大。2. 核心思想拆解前綴、后綴與部分匹配表要理解KMP的“智能”滑動(dòng)關(guān)鍵在于弄懂它如何利用已匹配的信息。這依賴于一個(gè)核心概念最長(zhǎng)相等前后綴以及由此構(gòu)建的部分匹配表Partial Match Table通常也被稱為next數(shù)組。2.1 理解“最長(zhǎng)相等前后綴”首先我們需要明確前綴和后綴的定義。對(duì)于一個(gè)字符串“ABCDABD”前綴指除了最后一個(gè)字符以外該字符串的所有頭部子串。例如”A”, “AB”, “ABC”, “ABCD”, “ABCDA”, “ABCDAB”。后綴指除了第一個(gè)字符以外該字符串的所有尾部子串。例如”D”, “BD”, “ABD”, “DABD”, “CDABD”, “BCDABD”。最長(zhǎng)相等前后綴就是指這個(gè)字符串中最長(zhǎng)的、相等的前綴子串和后綴子串的長(zhǎng)度。讓我們以模式串“ABCDABD”為例逐步計(jì)算每個(gè)位置考慮以該位置結(jié)尾的子串的最長(zhǎng)相等前后綴長(zhǎng)度“A”沒有前綴和后綴因?yàn)橐蠓亲陨黹L(zhǎng)度為0?！癆B”前綴[“A”]后綴[“B”]無相等長(zhǎng)度為0?！癆BC”前綴[“A”, “AB”]后綴[“C”, “BC”]無相等長(zhǎng)度為0?！癆BCD”前綴[“A”, “AB”, “ABC”]后綴[“D”, “CD”, “BCD”]無相等長(zhǎng)度為0。“ABCDA”前綴[“A”, “AB”, “ABC”, “ABCD”]后綴[“A”, “DA”, “CDA”, “BCDA”]。相等的有前綴“A”和后綴“A”長(zhǎng)度為1?！癆BCDAB”前綴[“A”, “AB”, “ABC”, “ABCD”, “ABCDA”]后綴[“B”, “AB”, “DAB”, “CDAB”, “BCDAB”]。相等的有前綴“AB”和后綴“AB”長(zhǎng)度為2?！癆BCDABD”前綴[“A”, … , “ABCDAB”]后綴[“D”, … , “BCDABD”]。無相等長(zhǎng)度為0。將每個(gè)位置的長(zhǎng)度記錄下來就得到了一個(gè)數(shù)組[0, 0, 0, 0, 1, 2, 0]。這個(gè)數(shù)組就是部分匹配表的雛形。在實(shí)際的KMP實(shí)現(xiàn)中我們通常使用一個(gè)叫next的數(shù)組它和部分匹配表有細(xì)微的差別但核心思想同源。一個(gè)常見的next數(shù)組定義是next[j]表示當(dāng)模式串中第j個(gè)字符與主串失配時(shí)模式串需要跳轉(zhuǎn)到的下一個(gè)比較位置。其構(gòu)建過程同樣依賴于最長(zhǎng)相等前后綴的思想。注意這里初學(xué)者最容易混淆的就是“部分匹配表”PMT和“next數(shù)組”的關(guān)系。PMT[i]的值是子串pattern[0...i]的最長(zhǎng)相等前后綴長(zhǎng)度。而next[i]通常表示當(dāng)pattern[i]匹配失敗時(shí)下一個(gè)應(yīng)該用pattern[next[i]]來與主串當(dāng)前字符比較。因此next[i] PMT[i-1]對(duì)于i0。很多資料和代碼實(shí)現(xiàn)直接混用這兩個(gè)概念理解時(shí)務(wù)必清楚你看到的是哪一種定義。下文我們將采用更通用的next數(shù)組進(jìn)行講解。2.2 next數(shù)組的構(gòu)建原理與代碼實(shí)現(xiàn)next數(shù)組是KMP算法的靈魂它決定了匹配失敗時(shí)模式串如何“跳躍”。其定義如下next[0] -1。這是一個(gè)特殊約定表示如果模式串的第一個(gè)字符就不匹配那么主串指針后移模式串指針歸零通過j next[j]會(huì)變?yōu)?1隨后在循環(huán)中會(huì)歸零并主串指針后移。對(duì)于j 0next[j]的值是在子串pattern[0...j-1]中其最長(zhǎng)相等前后綴的長(zhǎng)度。為什么是這個(gè)定義想象一下當(dāng)我們?cè)谀Ｊ酱牡趈位匹配失敗時(shí)說明前j位pattern[0...j-1]是和主串對(duì)應(yīng)部分匹配成功的。那么在模式串自身中pattern[0...j-1]這個(gè)子串的前綴和后綴如果有重合部分就意味著我們可以將前綴部分對(duì)齊到剛才匹配成功的后綴部分從而跳過不必要的比較。計(jì)算next數(shù)組本身也是一個(gè)模式匹配過程可以看作模式串與自身進(jìn)行匹配。下面是經(jīng)典的構(gòu)建代碼C風(fēng)格及其逐行解析void getNext(const string pattern, vectorint next) { int j 0; // 指向前綴的末尾位置也代表當(dāng)前已匹配的長(zhǎng)度 int k -1; // 指向后綴的末尾位置相對(duì)概念初始化為-1 next[0] -1; // 初始化 while (j pattern.length() - 1) { // 注意是 length-1因?yàn)?next[j] 計(jì)算的是 j 之前子串的信息 if (k -1 || pattern[j] pattern[k]) { // 情況1: k為-1表示從頭開始匹配情況2: 當(dāng)前字符匹配成功 j; k; // 這是最核心的賦值next[j] k // 含義當(dāng) pattern[j] 失配時(shí)下一個(gè)比較位置是 pattern[k] next[j] k; } else { // 當(dāng)前字符匹配失敗利用已有的 next 信息回溯 k k next[k]; } } }代碼邏輯深度解析初始化j0, k-1, next[0]-1。j是主指針遍歷模式串k可以理解為“待匹配的前綴末尾”初始化為-1。匹配成功的情況(pattern[j] pattern[k])當(dāng)j和k位置的字符相等時(shí)說明我們找到了一個(gè)更長(zhǎng)的相等前后綴。此時(shí)先讓j和k都自增然后設(shè)置next[j] k。這意味著對(duì)于新的位置j注意此時(shí)j已經(jīng)指向下一個(gè)待處理字符如果它匹配失敗我們可以回退到位置k繼續(xù)比較。因?yàn)閜attern[0...k-1]已經(jīng)和pattern[j-k...j-1]相等了。匹配失敗的情況(pattern[j] ! pattern[k])此時(shí)k需要回溯。k next[k]這行代碼是理解KMP精妙之處的關(guān)鍵。它不是在暴力地讓k--而是利用已經(jīng)計(jì)算好的next信息將k回溯到上一個(gè)可能匹配的位置。這相當(dāng)于在模式串的子串中又進(jìn)行了一次KMP匹配。如果k回溯到-1則下一輪循環(huán)會(huì)進(jìn)入k-1的條件將j和k都向前推進(jìn)。一個(gè)簡(jiǎn)單的構(gòu)建示例模式串“ABABC”初始j0, k-1, next[0]-1j0:k-1-j1, k0, next[1]0j1:pattern[1](B) ! pattern[0](A)-knext[0]-1j1:k-1-j2, k0, next[2]0j2:pattern[2](A) pattern[0](A)-j3, k1, next[3]1j3:pattern[3](B) pattern[1](B)-j4, k2, next[4]2最終next數(shù)組為[-1, 0, 0, 1, 2]。實(shí)操心得手動(dòng)推算next數(shù)組是徹底理解KMP的最佳途徑。不要只看代碼一定要拿紙筆對(duì)一個(gè)短字符串如“aabaaf”完整推演一遍next數(shù)組的構(gòu)建過程。你會(huì)深刻體會(huì)到k next[k]這行代碼如何高效地利用已知信息避免重復(fù)比較。3. 匹配過程詳解主串指針永不回退有了next數(shù)組匹配過程就變得清晰高效。核心是主串的指針i永不回退只通過調(diào)整模式串的指針j來實(shí)現(xiàn)滑動(dòng)。匹配過程的偽代碼如下int kmpSearch(const string text, const string pattern) { vectorint next(pattern.length()); getNext(pattern, next); // 構(gòu)建next數(shù)組 int i 0; // 主串 text 的指針 int j 0; // 模式串 pattern 的指針 while (i text.length() j (int)pattern.length()) { // 注意j可能為-1需強(qiáng)制轉(zhuǎn)換比較 if (j -1 || text[i] pattern[j]) { // 當(dāng)前字符匹配成功或者j-1意味著模式串需要從頭開始匹配 i; j; } else { // 當(dāng)前字符匹配失敗根據(jù)next數(shù)組移動(dòng)模式串指針j j next[j]; } } // 判斷匹配結(jié)果 if (j pattern.length()) { return i - j; // 返回匹配成功的起始位置 } else { return -1; // 未找到 } }匹配過程情景模擬 假設(shè)主串text “BBC ABCDAB ABCDABCDABDE”模式串pattern “ABCDABD”其next數(shù)組為[-1, 0, 0, 0, 0, 1, 2]這是另一種常見寫法next[0]-1。初始i0, j0。text[0]‘B’ pattern[0]‘A’不匹配。j next[0] -1。進(jìn)入下一輪循環(huán)j -1條件成立執(zhí)行i (i1), j (j0)。text[1]‘B’ pattern[0]‘A’不匹配。j next[0] -1。重復(fù)步驟2直到i4text[4]‘A’ pattern[0]‘A’匹配成功。i, j。后續(xù)text[5]‘B’ 對(duì) pattern[1]‘B’text[6]‘C’ 對(duì) pattern[2]‘C’… 一路匹配到i10, j6。此時(shí)text[10]‘ ’空格 pattern[6]‘D’匹配失敗。關(guān)鍵步驟j next[6] 2。這意味著我們不需要把模式串挪到text[5]重新開始暴力匹配的做法而是將模式串的指針j回退到2。此時(shí)模式串的前兩個(gè)字符“AB”已經(jīng)和主串中text[8...9]的“AB”對(duì)齊了。因?yàn)閚ext[6]2告訴我們?cè)谝哑ヅ涞摹癆BCDAB”中有長(zhǎng)度為2的相等前后綴“AB”。繼續(xù)比較text[10]‘ ’ 與 pattern[2]‘A’不匹配。j next[2] 0。text[10]‘ ’ 與 pattern[0]‘A’不匹配。j next[0] -1。j-1執(zhí)行i (i11), j (j0)重新開始新一輪匹配… 最終當(dāng)i15, j再次走到模式串末尾時(shí)匹配成功。整個(gè)過程中主串指針i從4開始到匹配成功時(shí)i22只前進(jìn)了18步期間從未回退。而暴力匹配算法在此例中主串指針會(huì)有大量的回退操作。4. 算法優(yōu)化next數(shù)組的優(yōu)化上述標(biāo)準(zhǔn)KMP算法中的next數(shù)組還有一個(gè)可以優(yōu)化的地方?？紤]模式串“AAAAAB”和主串“AAAAAAC…”。當(dāng)匹配到最后一個(gè)字符時(shí)‘B’對(duì)‘C’失敗根據(jù)next數(shù)組j會(huì)回退到前面的‘A’但回退后的字符依然是‘A’肯定和主串的‘C’不匹配會(huì)引發(fā)連續(xù)多次不必要的回退。優(yōu)化的思路是在構(gòu)建next數(shù)組時(shí)如果發(fā)現(xiàn)回退后的字符與當(dāng)前字符相同那么這次回退也是徒勞的應(yīng)該直接回退到更前的位置。即當(dāng)pattern[j] pattern[k]時(shí)我們不是簡(jiǎn)單地令next[j] k而是令next[j] next[k]。這樣構(gòu)建的數(shù)組有時(shí)被稱為nextval數(shù)組。優(yōu)化后的getNext函數(shù)如下void getNextVal(const string pattern, vectorint next) { int j 0; int k -1; next[0] -1; while (j pattern.length() - 1) { if (k -1 || pattern[j] pattern[k]) { j; k; // 優(yōu)化點(diǎn)如果回退后的字符相同則直接使用更早的回退位置 if (pattern[j] ! pattern[k]) { next[j] k; } else { next[j] next[k]; } } else { k next[k]; } } }對(duì)于模式串“AAAAAB”優(yōu)化后的nextval數(shù)組為[-1, -1, -1, -1, -1, 4]。當(dāng)?shù)谖鍌€(gè)‘A’j4匹配失敗時(shí)直接跳轉(zhuǎn)到nextval[4] -1相當(dāng)于模式串開頭避免了中間‘A’的多次無效比較。優(yōu)化后的KMP算法在模式串含有大量重復(fù)字符時(shí)效率更高。5. 復(fù)雜度分析與應(yīng)用場(chǎng)景時(shí)間復(fù)雜度構(gòu)建next數(shù)組O(m)其中 m 是模式串長(zhǎng)度。雖然代碼中有兩層循環(huán)但內(nèi)層k next[k]的回退操作使得k值減少的總次數(shù)不會(huì)超過j增加的總次數(shù)因此是線性的。匹配過程O(n)其中 n 是主串長(zhǎng)度。同理主串指針i只增不減模式串指針j的回退總次數(shù)也是有限的。總復(fù)雜度O(m n)。這是一個(gè)非常優(yōu)秀的線性復(fù)雜度。空間復(fù)雜度O(m)用于存儲(chǔ)next數(shù)組。應(yīng)用場(chǎng)景文本編輯器中的查找/替換功能這是最直觀的應(yīng)用KMP能快速在長(zhǎng)篇文檔中定位關(guān)鍵詞。生物信息學(xué)在DNA、RNA或蛋白質(zhì)序列中搜索特定的模式串如基因片段。網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)快速匹配數(shù)據(jù)包中的攻擊特征碼。拼寫檢查與語法糾錯(cuò)在詞典中快速查找單詞。字符串解析與模板引擎高效地識(shí)別和替換字符串中的特定模式。注意事項(xiàng)雖然KMP理論復(fù)雜度低但在實(shí)際應(yīng)用中尤其是模式串較短、字符集較大如隨機(jī)英文文本時(shí)其常數(shù)開銷構(gòu)建next數(shù)組、復(fù)雜的指針操作可能使得其實(shí)際性能并不比高度優(yōu)化的暴力算法如Boyer-Moore算法、Sunday算法等快。因此選擇字符串匹配算法需要結(jié)合實(shí)際場(chǎng)景和數(shù)據(jù)特征。6. 常見問題與排查技巧實(shí)錄在實(shí)際實(shí)現(xiàn)和面試中圍繞KMP算法的問題層出不窮。下面我整理了幾個(gè)最典型的問題和我的解決思路。問題1next數(shù)組構(gòu)建總是出錯(cuò)尤其是下標(biāo)邊界。排查這幾乎是每個(gè)初學(xué)者的必經(jīng)之路。關(guān)鍵在于理解next[j]存儲(chǔ)的是當(dāng)j位置匹配失敗時(shí)下一個(gè)要比較的位置。在代碼while (j pattern.length() - 1)中循環(huán)條件是j len-1因?yàn)槲覀冊(cè)谘h(huán)體內(nèi)計(jì)算的是next[j1]。如果你寫成j pattern.length()就會(huì)數(shù)組越界。畫圖把j,k,pattern[j],pattern[k]的關(guān)系在紙上畫出來一步步跟蹤。技巧使用一個(gè)極短的字符串如“ABABA”進(jìn)行單元測(cè)試打印出每一步的j,k,next[j]值與手動(dòng)計(jì)算結(jié)果對(duì)比。問題2匹配函數(shù)陷入死循環(huán)或者匹配結(jié)果不對(duì)。排查首先檢查next數(shù)組是否正確。其次重點(diǎn)檢查匹配循環(huán)中的條件while (i text.length() j (int)pattern.length())。注意j可能等于-1而pattern.length()返回的是size_t無符號(hào)類型直接比較-1 pattern.length()在有些編譯器上會(huì)得到false因?yàn)?1會(huì)被轉(zhuǎn)換成一個(gè)大整數(shù)。所以必須將pattern.length()強(qiáng)制轉(zhuǎn)換為int或者將j聲明為int并與-1比較時(shí)單獨(dú)處理。技巧在匹配循環(huán)內(nèi)添加調(diào)試輸出打印每一步的i,j,text[i],pattern[j]觀察指針移動(dòng)是否符合預(yù)期。問題3理解了算法但寫代碼時(shí)還是感覺模糊。根本原因?qū)Α白铋L(zhǎng)相等前后綴”和“指針回退”的物理意義理解不夠透徹。next[j]k的本質(zhì)是在pattern[0...j-1]這個(gè)已匹配的子串中它的長(zhǎng)度為k的前綴pattern[0...k-1]恰好等于它的后綴pattern[j-k...j-1]。所以當(dāng)pattern[j]失敗時(shí)我們可以放心地把模式串向右滑動(dòng)讓它的前綴pattern[0...k-1]對(duì)齊到主串中剛剛匹配成功的后綴部分然后從pattern[k]開始繼續(xù)比較。最佳實(shí)踐不要死記硬背代碼。找3-5個(gè)不同的模式串如“abcabc”、“aabaaf”、“abababca”完整地、手工地執(zhí)行兩遍第一遍手工構(gòu)建next數(shù)組第二遍手工模擬匹配過程。這個(gè)過程比看十遍代碼都管用。問題4如何應(yīng)對(duì)多模式串匹配解答標(biāo)準(zhǔn)的單模式KMP無法直接處理。這時(shí)需要引入更強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)如Aho-Corasick自動(dòng)機(jī)AC自動(dòng)機(jī)。你可以把AC自動(dòng)機(jī)理解為KMP算法在多模式串情況下的擴(kuò)展它用Trie樹組織所有模式串并為每個(gè)節(jié)點(diǎn)構(gòu)建失敗指針Fail Pointer其思想與KMP的next數(shù)組一脈相承。當(dāng)在一個(gè)節(jié)點(diǎn)匹配失敗時(shí)就跳轉(zhuǎn)到它的失敗指針?biāo)傅墓?jié)點(diǎn)繼續(xù)匹配。學(xué)習(xí)KMP是理解AC自動(dòng)機(jī)的重要基礎(chǔ)。KMP算法是數(shù)據(jù)結(jié)構(gòu)與算法課程中的一個(gè)里程碑它第一次向我們展示了如何通過預(yù)處理模式串本身的信息來極大優(yōu)化匹配效率。理解它不僅僅是掌握一個(gè)算法更是學(xué)習(xí)一種“利用已知信息避免重復(fù)工作”的深刻思想。在以后遇到類似的匹配、搜索、狀態(tài)轉(zhuǎn)移問題時(shí)這種預(yù)處理和狀態(tài)回溯的思路會(huì)反復(fù)出現(xiàn)。我建議你在理解基本原理后嘗試自己從頭實(shí)現(xiàn)一遍并和暴力算法進(jìn)行性能對(duì)比感受其威力。遇到坑是必然的但爬出坑后的收獲會(huì)讓你對(duì)字符串處理有全新的認(rèn)識(shí)。