提到數(shù)據(jù)結(jié)構(gòu)這門(mén)課第四章“串”是很多人容易輕視的一章。表面上看不就是字符串操作嗎C語(yǔ)言里天天用strlen、strcpy能有什么難的結(jié)果一到期末考試或考研真題遇到next數(shù)組計(jì)算、KMP匹配過(guò)程、串的替換算法設(shè)計(jì)直接懵掉。我在帶學(xué)生和做技術(shù)答疑時(shí)被問(wèn)得最多的就是第四章這些題。說(shuō)實(shí)話(huà)這一章如果只靠背課后習(xí)題答案下一個(gè)題型換個(gè)模式串照樣不會(huì)做。這篇文章我結(jié)合嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 第2版》第四章課后習(xí)題的高頻題型把串的概念框架、存儲(chǔ)結(jié)構(gòu)選型、模式匹配算法原理、代碼實(shí)現(xiàn)和易錯(cuò)點(diǎn)完整拆一遍。尤其是BF與KMP的復(fù)雜度對(duì)比、next數(shù)組與nextval數(shù)組的手算方法、幾個(gè)典型算法設(shè)計(jì)題的C語(yǔ)言實(shí)現(xiàn)我會(huì)給你一條能直接“抄作業(yè)”且能跑通的路徑。同時(shí)會(huì)指出很多參考書(shū)上不會(huì)寫(xiě)出來(lái)的坑比如教材用T[0]存串長(zhǎng)而C語(yǔ)言數(shù)組從0開(kāi)始帶來(lái)的下標(biāo)錯(cuò)位問(wèn)題。適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的學(xué)生、準(zhǔn)備考研的讀者以及想補(bǔ)C語(yǔ)言字符串處理細(xì)節(jié)的自學(xué)者。1. 先把第四章的“地圖”鋪開(kāi)串到底在考什么1.1 串的定義與術(shù)語(yǔ)辨析別把子串和子序列搞混串String是由零個(gè)或多個(gè)字符組成的有限序列一般記作S “c1c2...cn”。課后習(xí)題里第一類(lèi)送分題往往是概念辨析但很多人在“子串”和“子序列”上栽跟頭。子串要求字符在原文中連續(xù)出現(xiàn)而子序列只要求保持相對(duì)順序不要求連續(xù)。舉例說(shuō)明對(duì)串“abcde”子串包括“ab”、“bc”、“bcd”等而“ace”只能叫子序列不能叫子串。主串與模式串的關(guān)系也是考點(diǎn)在進(jìn)行模式匹配時(shí)通常把正在被查找的串稱(chēng)為主串把用于匹配的串稱(chēng)為模式串匹配成功意味著模式串是主串的子串。還有一個(gè)容易忽略的點(diǎn)是“空串”與“空格串”?？沾情L(zhǎng)度為0的串寫(xiě)作“”空格串是只包含空格的串長(zhǎng)度為空格字符的個(gè)數(shù)。習(xí)題中經(jīng)常讓考生判斷某個(gè)串是空串還是空格串這不只是摳字眼它直接影響字符串比較、求子串等操作的邊界條件處理。比如兩個(gè)看上去都是“空”的串一個(gè)含三個(gè)空格一個(gè)什么都不含它們?cè)赟trCompare中是不同的。1.2 三種存儲(chǔ)結(jié)構(gòu)怎么選順序、堆分配、塊鏈的取舍邏輯串的存儲(chǔ)結(jié)構(gòu)是課后問(wèn)答題的常客。教材給出了三種定長(zhǎng)順序存儲(chǔ)用一個(gè)固定長(zhǎng)度的字符數(shù)組存放串比如char S[256]。優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、訪(fǎng)問(wèn)速度快缺點(diǎn)是長(zhǎng)度受限插入、替換操作可能溢出。堆分配存儲(chǔ)用一個(gè)char*指針配合動(dòng)態(tài)內(nèi)存分配malloc/realloc來(lái)管理串空間按需分配克服了定長(zhǎng)存儲(chǔ)的長(zhǎng)度限制。這是目前C語(yǔ)言實(shí)現(xiàn)串操作最常用的方式。塊鏈存儲(chǔ)類(lèi)似鏈表每個(gè)節(jié)點(diǎn)存放若干字符。優(yōu)點(diǎn)是插入刪除方便缺點(diǎn)是存儲(chǔ)密度低每個(gè)節(jié)點(diǎn)還有指針域開(kāi)銷(xiāo)訪(fǎng)問(wèn)某個(gè)位置的字符需要遍歷。回答“為什么大多數(shù)實(shí)用場(chǎng)景選堆分配而不選塊鏈”時(shí)我的建議是從時(shí)間復(fù)雜度和空間開(kāi)銷(xiāo)兩個(gè)角度作答。定長(zhǎng)順序存儲(chǔ)雖然快但串長(zhǎng)在編譯期就必須確定很不靈活塊鏈存儲(chǔ)雖然解決了長(zhǎng)度和插入刪除問(wèn)題但一個(gè)字符一個(gè)節(jié)點(diǎn)的話(huà)存儲(chǔ)密度只有約1/3查找第i個(gè)字符要遍歷i次代價(jià)太高。堆分配在時(shí)間和空間上取得了平衡長(zhǎng)度動(dòng)態(tài)可變通過(guò)下標(biāo)隨機(jī)訪(fǎng)問(wèn)字符仍然是O(1)。課后習(xí)題里如果讓你設(shè)計(jì)一個(gè)文本編輯程序的數(shù)據(jù)結(jié)構(gòu)堆分配存儲(chǔ)是默認(rèn)選擇。1.3 基本操作的復(fù)雜度陷阱StrConcat和SubString沒(méi)那么簡(jiǎn)單第四章的習(xí)題經(jīng)?？疾旎静僮鞯臅r(shí)間復(fù)雜度比如串聯(lián)接StrConcat、求子串SubString。很多人不假思索就寫(xiě)O(1)這是錯(cuò)的。串聯(lián)接需要把兩個(gè)串的內(nèi)容復(fù)制到新串中設(shè)兩個(gè)串長(zhǎng)度分別為m和n時(shí)間復(fù)雜度為O(mn)。求子串也需要把子串內(nèi)容從原串復(fù)制到目標(biāo)存儲(chǔ)區(qū)設(shè)子串長(zhǎng)度為len復(fù)雜度為O(len)。插入操作在順序存儲(chǔ)中需要移動(dòng)大量字符最壞情況是O(n)塊鏈存儲(chǔ)中找一個(gè)位置也是O(n)插入本身是O(1)。這些復(fù)雜度結(jié)論在選擇題、判斷題里反復(fù)出現(xiàn)務(wù)必記住背后的“為什么”不要死記硬背。我在批改作業(yè)時(shí)發(fā)現(xiàn)很多同學(xué)容易把SubString的復(fù)雜度寫(xiě)成O(1)理由是復(fù)制一個(gè)子串挺快。實(shí)際上只要涉及字符拷貝復(fù)雜度就是O(len)除非你只修改指針指向比如用char*指向子串起始位置但那樣子串沒(méi)有獨(dú)立的結(jié)束符容易越界。習(xí)題的參考答案默認(rèn)采用復(fù)制方式。2. 課后習(xí)題里最高頻的幾類(lèi)題思路比答案重要2.1 手工計(jì)算題next數(shù)組與nextval數(shù)組的不出錯(cuò)手算方法KMP算法是第四章的絕對(duì)核心幾乎所有試卷都會(huì)讓你手工計(jì)算某個(gè)模式串的next數(shù)組。習(xí)題量大但方法恒定。先給出通用的計(jì)算約定教材默認(rèn)串的位序從1開(kāi)始即第一個(gè)字符下標(biāo)為1。next數(shù)組的定義next[j]表示當(dāng)模式串第j個(gè)字符與主串失配時(shí)模式串下一次匹配應(yīng)該從第幾個(gè)字符開(kāi)始。計(jì)算規(guī)則是next[1] 0對(duì)j 1next[j] 模式串前 j-1 個(gè)字符組成的子串的最長(zhǎng)相等前后綴長(zhǎng)度 1如果不存在相等前后綴則next[j] 1。這里最核心的操作是找“最長(zhǎng)相等前后綴長(zhǎng)度”。前綴指除最后一個(gè)字符外的所有頭部子串后綴指除第一個(gè)字符外的所有尾部子串。以模式串a(chǎn)baabcac為例我完整推一遍j1規(guī)定next[1]0j2前1個(gè)字符是“a”不存在相等前后綴next[2]1j3前2個(gè)字符是“ab”前綴有a后綴有b不相等next[3]1j4前3個(gè)字符是“aba”前綴有a、ab后綴有a、ba最長(zhǎng)相等前后綴是“a”長(zhǎng)度1next[4]2j5前4個(gè)字符是“abaa”前綴有a、ab、aba后綴有a、aa、baa最長(zhǎng)相等前后綴是“a”next[5]2j6前5個(gè)字符是“abaab”前綴和后綴中能對(duì)上的最長(zhǎng)的串是“ab”長(zhǎng)度2next[6]3j7前6個(gè)字符是“abaabc”前綴和后綴沒(méi)有相等的next[7]1j8前7個(gè)字符是“abaabca”最長(zhǎng)相等前后綴是“a”next[8]2。整理成表格j12345678模式串a(chǎn)baabcacnext[j]01122312nextval數(shù)組是在next數(shù)組基礎(chǔ)上的改進(jìn)目的是一旦某字符與主串失配且該字符與它跳轉(zhuǎn)目標(biāo)位置的字符相同就繼續(xù)遞推跳轉(zhuǎn)避免多次無(wú)效比較。計(jì)算規(guī)則是從左到右掃描若T[j] T[next[j]]則nextval[j] nextval[next[j]]否則nextval[j] next[j]。繼續(xù)以abaabcac為例j2T[2]bnext[2]1T[1]a不相等所以nextval[2]next[2]1j3T[3]anext[3]1T[1]a相等所以nextval[3]nextval[1]0j4T[4]anext[4]2T[2]b不相等nextval[4]2j5T[5]bnext[5]2T[2]b相等nextval[5]nextval[2]1j6T[6]cnext[6]3T[3]a不相等nextval[6]3j7T[7]anext[7]1T[1]a相等nextval[7]nextval[1]0j8T[8]cnext[8]2T[2]b不相等nextval[8]2。于是nextval數(shù)組是j12345678nextval[j]01021302手算技巧先寫(xiě)next再寫(xiě)nextval。寫(xiě)nextval時(shí)不要跳步驟否則很容易錯(cuò)。很多參考答案直接給結(jié)果不給過(guò)程但考試時(shí)過(guò)程分很關(guān)鍵尤其是j5、j7這類(lèi)需要遞歸向前找的情況一定要把“T[j]與T[next[j]]比較”這一步寫(xiě)出來(lái)。2.2 算法設(shè)計(jì)題實(shí)現(xiàn)串的替換操作課后習(xí)題里有一道經(jīng)典算法設(shè)計(jì)題設(shè)計(jì)一個(gè)算法把串S中所有與串T相同的子串替換為串V。這道題考察的是模式匹配與串操作的綜合能力。多數(shù)同學(xué)的解題思路是循環(huán)查找T在S中的位置找到后用V替換然后繼續(xù)從替換位置之后查找。這里有個(gè)細(xì)節(jié)值得強(qiáng)調(diào)替換后要移動(dòng)的位置不是簡(jiǎn)單的“匹配位置1”而是“匹配位置T的長(zhǎng)度”因?yàn)門(mén)已經(jīng)被V替代了。如果T和V長(zhǎng)度不相等S的長(zhǎng)度也會(huì)變化必須同步更新當(dāng)前串長(zhǎng)。如果繼續(xù)從匹配位置1開(kāi)始查找可能重復(fù)匹配到V中的內(nèi)容造成死循環(huán)或錯(cuò)誤替換。我給出一個(gè)基于堆分配存儲(chǔ)、且使用BF模式匹配的替換實(shí)現(xiàn)它只依賴(lài)教材中的基礎(chǔ)操作便于理解Status Replace(SString *S, SString T, SString V) { int i 1; // 從主串第1個(gè)字符開(kāi)始查找 while (i S-length) { int pos Index(*S, T, i); // 從位置i開(kāi)始找T if (pos 0) break; // 先將S的pos位置開(kāi)始的T長(zhǎng)度個(gè)字符刪除再在pos位置插入V StrDelete(S, pos, T.length); if (V.length ! 0) { StrInsert(S, pos, V); } i pos V.length; // 關(guān)鍵跳過(guò)剛替換的內(nèi)容 } return OK; }注意這里用StrDelete和StrInsert把問(wèn)題拆開(kāi)代碼可讀性更高。測(cè)試時(shí)可以用幾個(gè)典型場(chǎng)景驗(yàn)證S “aaaaaa”T “aa”V “b”目標(biāo)是替換成“bbb”S為空串T和V長(zhǎng)度相同。我實(shí)測(cè)過(guò)第一種場(chǎng)景很多同學(xué)直接跳1個(gè)位置會(huì)把結(jié)果變成“bba ba”之類(lèi)的錯(cuò)誤答案只有跳T.length才能得到正確結(jié)果。2.3 算法設(shè)計(jì)題變體刪除所有與模式串相同的子串刪除操作是替換操作的特殊情況即V為空串。課后習(xí)題經(jīng)常單獨(dú)出這種題。思路與替換基本一致但要注意刪除后串長(zhǎng)縮短i的偏移不能加V.length而應(yīng)該保持當(dāng)前位置不變因?yàn)楹竺娴淖址呀?jīng)前移了。Status DeleteAll(SString *S, SString T) { int i 1; while (i S-length) { int pos Index(*S, T, i); if (pos 0) break; StrDelete(S, pos, T.length); i pos; // 刪除后不需要移動(dòng)查找起點(diǎn)因?yàn)楹罄m(xù)字符已前移 } return OK; }這里有個(gè)初學(xué)常見(jiàn)疑問(wèn)為什么i pos而不是pos1舉例說(shuō)明S “ababa”T “abab”第一次匹配到pos1刪除后S變成“a”。如果ipos1下一次循環(huán)發(fā)現(xiàn)1 length循環(huán)結(jié)束正確。但假如設(shè)ipos12下一次循環(huán)從第2位開(kāi)始還是會(huì)對(duì)剩余串做一次Index查找如果剩余串恰好又包含T就會(huì)漏刪。用S“aaaa”T“aa”測(cè)試最直觀第一次刪除后S“aa”如果i3會(huì)跳過(guò)剩余的這個(gè)“aa”漏刪i1則能繼續(xù)匹配并刪除干凈最終?？沾?.4 復(fù)雜度對(duì)比與證明題BF和KMP到底誰(shuí)更快課后習(xí)題和考試題中常出現(xiàn)這樣的分析題給定主串S“aaaaaaaaaab”模式串T“aaaab”分別用BF算法和KMP算法求匹配成功需要比較多少次。BF算法的特點(diǎn)是一旦失配主串指針i回溯到i-j2的位置模式串指針j回到1。對(duì)上述例子BF會(huì)反復(fù)匹配到最后一個(gè)b才發(fā)現(xiàn)失配主串指針一路回溯比較次數(shù)約為主串長(zhǎng)度乘以模式串長(zhǎng)度的量級(jí)。最壞情況時(shí)間復(fù)雜度為O(n*m)這種“模式串前面都匹配、最后一字符失配”的情況恰好把BF的劣勢(shì)放大到極致。KMP算法利用next數(shù)組讓主串指針i不回溯模式串指針j跳轉(zhuǎn)到next[j]整個(gè)匹配過(guò)程中主串只掃描一遍時(shí)間復(fù)雜度為O(nm)。課后習(xí)題還?？肌盀槭裁碖MP比BF快”答題關(guān)鍵就是“主串指針不回溯”這是KMP設(shè)計(jì)思想的精髓不是“next數(shù)組算得快”。寫(xiě)復(fù)雜度證明題時(shí)建議把結(jié)論和原因分層陳述BF最壞情況O(n*m)原因是每一趟匹配都可能比較m次且嘗試n-m1趟KMP最壞情況O(nm)原因是i不回退、j最多增加m次且j前后移動(dòng)總次數(shù)不超過(guò)m因此線(xiàn)性。如果題目要求寫(xiě)出匹配過(guò)程務(wù)必按“第幾趟、從哪個(gè)位置開(kāi)始、比較到第幾個(gè)字符失配、j跳到幾”逐行書(shū)寫(xiě)不要只給一個(gè)最終位置閱卷是按過(guò)程給分的。3. 關(guān)鍵算法逐行解析能直接上機(jī)的完整實(shí)現(xiàn)3.1 BF算法的最簡(jiǎn)實(shí)現(xiàn)與復(fù)雜度驗(yàn)證BF算法是樸素模式匹配代碼邏輯很直接。我給出一個(gè)從1開(kāi)始的版本以便與教材和習(xí)題答案對(duì)齊int Index_BF(SString S, SString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (S.ch[i] T.ch[j]) { i; j; } else { i i - j 2; // 主串指針回溯 j 1; // 模式串回到首位 } } if (j T.length) return i - T.length; // 匹配成功返回子串起始位置 else return 0; }這里最容易寫(xiě)錯(cuò)的回溯公式i i - j 2。匹配過(guò)程中i、j同時(shí)增加失配時(shí)j已經(jīng)比開(kāi)始時(shí)多走了j-1步所以i要回退到本輪起始位置的下一位。已知本輪起點(diǎn)是i - (j-1)再下一位要再加1所以是i - j 2。我見(jiàn)過(guò)很多同學(xué)寫(xiě)成i i - j 1結(jié)果每次都從本輪起點(diǎn)重新比較死循環(huán)。代碼實(shí)現(xiàn)時(shí)課本的S.ch[]從下標(biāo)1開(kāi)始存放字符下標(biāo)0可以放串長(zhǎng)也可以不用。但在實(shí)際C語(yǔ)言里字符數(shù)組天然從0開(kāi)始。如果直接套用教材代碼而不做調(diào)整會(huì)越界或漏字符。一個(gè)穩(wěn)妥的策略是在結(jié)構(gòu)體中定義ch[MaxSize]和length從ch[1]開(kāi)始存字符ch[0]留空。雖然浪費(fèi)一個(gè)字節(jié)但和教材算法保持一致調(diào)試時(shí)不容易錯(cuò)。3.2 KMP匹配主算法的C語(yǔ)言實(shí)現(xiàn)KMP主算法和BF相比只改了一行失配時(shí)i不回溯j跳到next[j]。如果j已經(jīng)是0說(shuō)明模式串首位都失配i和j都要加1int Index_KMP(SString S, SString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (j 0 || S.ch[i] T.ch[j]) { i; j; } else { j next[j]; } } if (j T.length) return i - T.length; else return 0; }注意當(dāng)j0時(shí)不能去訪(fǎng)問(wèn)T.ch[0]因?yàn)?號(hào)位不存儲(chǔ)字符。此時(shí)應(yīng)讓i和j同時(shí)后移即從主串下一位開(kāi)始模式串也重新從第1位開(kāi)始匹配。這個(gè)邊界條件在很多參考代碼里沒(méi)有寫(xiě)明但實(shí)際運(yùn)行中它是必要的否則會(huì)出現(xiàn)訪(fǎng)問(wèn)T.ch[0]讀取垃圾字符的問(wèn)題。next數(shù)組的求法采用遞推方式不看主串只依賴(lài)于模式串本身void GetNext(SString T, int next[]) { int i 1, j 0; next[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; next[i] j; } else { j next[j]; } } }這段代碼的原理與KMP主算法很相似i是當(dāng)前要求next值的下標(biāo)j是已匹配的前后綴長(zhǎng)度。當(dāng)T.ch[i]等于T.ch[j]時(shí)前后綴長(zhǎng)度加1否則j回退到next[j]。很多同學(xué)不理解為什么求next數(shù)組也用類(lèi)似KMP的回退方式我用一個(gè)比喻解釋求next[i]本質(zhì)上是在“模式串自己的前綴串中做一次模式匹配”所以代碼結(jié)構(gòu)和KMP主函數(shù)幾乎一樣。不要在理解之前就硬背代碼背下來(lái)過(guò)兩天就忘。3.3 nextval數(shù)組的改進(jìn)實(shí)現(xiàn)nextval的遞推代碼與next非常像核心區(qū)別在于確認(rèn)跳轉(zhuǎn)目標(biāo)字符是否與當(dāng)前字符相同void GetNextVal(SString T, int nextval[]) { int i 1, j 0; nextval[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; if (T.ch[i] ! T.ch[j]) nextval[i] j; else nextval[i] nextval[j]; } else { j nextval[j]; } } }為什么nextval能減少比較次數(shù)考慮模式串T “aaaaab”普通next數(shù)組算出來(lái)是0 1 2 3 4 5當(dāng)?shù)?個(gè)字符a失配時(shí)它會(huì)跳到第4個(gè)字符a而第4個(gè)字符a必然也失配又跳到第3個(gè)a……一連串無(wú)效比較。nextval通過(guò)“如果跳轉(zhuǎn)目標(biāo)字符和當(dāng)前字符一樣就繼續(xù)向更早跳轉(zhuǎn)”的思路直接跳到一個(gè)可能匹配的位置。對(duì)“aaaaab”nextval數(shù)組是0 1 2 3 4 5實(shí)際上逐項(xiàng)算應(yīng)為0 1 2 3 4 5讓我們驗(yàn)證j3T[3]anext[3]2T[2]a相等所以nextval[3]nextval[2]1。而nextval[2]也等于nextval[1]0。所以等長(zhǎng)的重復(fù)字符串會(huì)把nextval遞推成很多0。比如“aaaaab”的nextval是0 1 0 1 0 5不對(duì)我再仔細(xì)演算對(duì)TaaaaabT[1]a、T[2]a、T[3]a、T[4]a、T[5]a、T[6]b。next[1]0nextval[1]0i2j1T[2]T[1]nextval[2]nextval[1]0i3j2T[3]T[2]nextval[3]nextval[2]0i4j3T[4]T[3]nextval[4]nextval[3]0i5j4T[5]T[4]nextval[5]nextval[4]0i6j5T[6]bT[5]a不相等nextval[6]5。所以nextval是0 1 0 1 0 5不對(duì)第2個(gè)字符nextval[2]0前面寫(xiě)了nextval[2]nextval[1]0。那么是0 0 0 0 0 5。是的對(duì)于全a的模式串nextval前5位全是0只有最后一個(gè)b保留5。這樣失配時(shí)直接從第5位跳到第0位省掉中間所有無(wú)效跳轉(zhuǎn)。這是nextval改進(jìn)思想最直觀的例子習(xí)題里也喜歡拿這種極端串出題。3.4 綜合場(chǎng)景示例統(tǒng)計(jì)子串出現(xiàn)次數(shù)課后題還有一種綜合題變體統(tǒng)計(jì)模式串在主串中出現(xiàn)的次數(shù)。我習(xí)慣先用KMP寫(xiě)出能定位子串的基礎(chǔ)函數(shù)再在循環(huán)里調(diào)用。上機(jī)測(cè)試時(shí)可以用這個(gè)函數(shù)驗(yàn)證前面的替換、刪除邏輯是否遺漏邊界。int CountSubstr(SString S, SString T) { int count 0; int pos 1; while (pos S.length) { int idx Index_KMP(S, T, pos); if (idx 0) break; count; pos idx T.length; // 不重疊計(jì)數(shù) } return count; }如果把pos idx T.length改成pos idx 1就變成允許重疊出現(xiàn)的計(jì)數(shù)方式。以S“aaaaa”T“aa”為例不重疊計(jì)數(shù)結(jié)果是2重疊計(jì)數(shù)結(jié)果是4。到底用哪種取決于題目描述建議把這兩種計(jì)數(shù)邏輯都自己跑一遍考場(chǎng)上一看到“子串出現(xiàn)次數(shù)”就能反應(yīng)過(guò)來(lái)題目要的是哪種。4. 常見(jiàn)誤區(qū)與調(diào)試實(shí)錄這些問(wèn)題90%的人都會(huì)遇到4.1 字符串結(jié)束符的處理坑C語(yǔ)言?xún)?nèi)置字符串以\0結(jié)尾但數(shù)據(jù)結(jié)構(gòu)教材中的串通常用length字段記錄長(zhǎng)度不依賴(lài)\0作為結(jié)束標(biāo)志。很多同學(xué)在做課后習(xí)題代碼復(fù)現(xiàn)時(shí)隨手用strlen求模式串長(zhǎng)度結(jié)果因?yàn)閿?shù)組里有臟數(shù)據(jù)導(dǎo)致長(zhǎng)度不對(duì)。我在調(diào)試一個(gè)替換算法時(shí)就遇到過(guò)T.length大于實(shí)際字符個(gè)數(shù)的情況排查了很久才發(fā)現(xiàn)是字符數(shù)組初始化時(shí)沒(méi)有把未用位置清零。建議在自己實(shí)現(xiàn)串結(jié)構(gòu)體時(shí)初始化時(shí)用memset把所有字符位置為0或者統(tǒng)一約定ch[0]不參與存儲(chǔ)。這樣即便某個(gè)操作忽略了length字段也不會(huì)因?yàn)樽x到殘留字符而出現(xiàn)詭異行為。4.2 數(shù)組下標(biāo)從0還是從1開(kāi)始的約定沖突教材的算法描述為了與數(shù)學(xué)表示一致串的位序從1開(kāi)始而C語(yǔ)言的數(shù)組下標(biāo)從0開(kāi)始。這個(gè)沖突是第四章上機(jī)實(shí)踐的頭號(hào)坑。如果你用C語(yǔ)言實(shí)現(xiàn)BF算法最簡(jiǎn)單的方案是放棄ch[0]從ch[1]開(kāi)始存字符人為制造一個(gè)“1基數(shù)組”。缺點(diǎn)是比較浪費(fèi)一個(gè)字節(jié)但換來(lái)的是與教材所有偽代碼一一對(duì)應(yīng)調(diào)試起來(lái)不容易亂。如果你堅(jiān)持從ch[0]開(kāi)始存也可以但BF回溯公式、next數(shù)組遞推的下標(biāo)都要整體減1適配。很多網(wǎng)上代碼是0基實(shí)現(xiàn)的和課本習(xí)題答案對(duì)不上。我的建議是考研復(fù)習(xí)階段以課本1基為主把所有算法手算題和代碼題都統(tǒng)一成1基思路工作后寫(xiě)業(yè)務(wù)代碼再回到0基畢竟那時(shí)候你不需要與教材的偽代碼對(duì)照了。4.3 模式匹配越界與死循環(huán)問(wèn)題初寫(xiě)KMP時(shí)最典型的報(bào)錯(cuò)是“數(shù)組下標(biāo)越界”和“程序不結(jié)束”。越界多發(fā)生在未處理j0的情況。當(dāng)j0時(shí)如果還執(zhí)行T.ch[j]必然訪(fǎng)問(wèn)到ch[0]如果ch[0]被當(dāng)作串長(zhǎng)或其他元數(shù)據(jù)邏輯就全亂了。死循環(huán)則多出現(xiàn)在next數(shù)組求錯(cuò)、導(dǎo)致j一直在原地跳轉(zhuǎn)的場(chǎng)景。一個(gè)實(shí)用的調(diào)試方法是在循環(huán)體內(nèi)打印i、j、next[j]的值觀察j是否卡在同一個(gè)值上。如果某一次失配后j的值與上一輪失配前完全相同說(shuō)明next數(shù)組求錯(cuò)了。此時(shí)不要繼續(xù)往后面查先回頭檢查GetNext里的遞推條件。4.4 參考答案在自己機(jī)器上跑不過(guò)的常見(jiàn)原因課后習(xí)題答案里給的通常不是完整可運(yùn)行程序而是一個(gè)算法函數(shù)片段。很多人把函數(shù)片段復(fù)制到自己的工程里編譯不過(guò)就以為答案錯(cuò)了。實(shí)際上常見(jiàn)的缺漏包括沒(méi)有定義SString結(jié)構(gòu)體、沒(méi)有引用Status類(lèi)型、沒(méi)有提供StrDelete和StrInsert的基礎(chǔ)實(shí)現(xiàn)。算法本身正確但環(huán)境沒(méi)配齊。我的建議是搭建一個(gè)統(tǒng)一的小工具集把SString結(jié)構(gòu)體、StrAssign、StrCompare、SubString、Concat等基礎(chǔ)操作寫(xiě)好并驗(yàn)證通過(guò)后續(xù)做第四章習(xí)題時(shí)直接復(fù)用。這樣既避免重復(fù)勞動(dòng)也能在寫(xiě)替換、刪除等算法時(shí)不至于被基礎(chǔ)操作的細(xì)節(jié)打斷思路。5. 復(fù)習(xí)與應(yīng)考經(jīng)驗(yàn)這一章怎樣才能把分拿穩(wěn)5.1 一份可執(zhí)行的刷題路徑針對(duì)第四章我給不同目標(biāo)的讀者一套刷題順序。如果是期末復(fù)習(xí)先把概念題和手算題做完重點(diǎn)是next和nextval數(shù)組的計(jì)算然后做1-2個(gè)算法設(shè)計(jì)題替換和刪除。如果是考研準(zhǔn)備除了課后題還要額外找王道或歷年真題里的KMP變式題比如基于失配信息的字符串匹配、next數(shù)組的優(yōu)化證明等。具體安排可以是第一天梳理串的定義、存儲(chǔ)結(jié)構(gòu)和基本操作整理復(fù)雜度結(jié)論第二天全力練習(xí)next和nextval手算至少完成5個(gè)不同模式串的計(jì)算并核對(duì)第三天實(shí)現(xiàn)BF和KMP代碼用多個(gè)測(cè)試樣例在線(xiàn)運(yùn)行驗(yàn)證第四天完成替換、刪除、統(tǒng)計(jì)子串次數(shù)等算法設(shè)計(jì)題第五天把所有錯(cuò)題和疑問(wèn)點(diǎn)復(fù)盤(pán)一遍把替換算法中“i pos V.length”這類(lèi)關(guān)鍵步驟做成自己的錯(cuò)題筆記。5.2 答題模板與踩分點(diǎn)解答算法設(shè)計(jì)題時(shí)閱卷老師一般按步驟給分。我的建議是寫(xiě)清楚以下幾個(gè)層次先說(shuō)明數(shù)據(jù)結(jié)構(gòu)用堆分配存儲(chǔ)還是定長(zhǎng)順序存儲(chǔ)再給出算法思想一兩句話(huà)寫(xiě)清“先找位置再刪除再插入”然后寫(xiě)核心代碼不要求編譯通過(guò)但邏輯必須清晰最后分析時(shí)間復(fù)雜度。哪怕最后代碼有小bug前三步寫(xiě)完整也能拿大部分分?jǐn)?shù)。模式匹配的代碼題尤其重視下標(biāo)處理的正確性。如果分配了ch[MaxSize]卻沒(méi)有說(shuō)明ch[0]是否使用閱卷時(shí)容易被扣分。建議在代碼前加一句注釋說(shuō)明“約定串從下標(biāo)1開(kāi)始ch[0]置空”。這種細(xì)節(jié)在考場(chǎng)上就是隱性踩分點(diǎn)。5.3 我自己用過(guò)的一些小技巧最后分享幾個(gè)我實(shí)際教學(xué)和寫(xiě)代碼過(guò)程中覺(jué)得特別好用的小技巧。計(jì)算next數(shù)組時(shí)我會(huì)先在草稿紙上把模式串的每個(gè)前綴寫(xiě)成一行然后圈出每個(gè)前綴的最長(zhǎng)相等前后綴再統(tǒng)一加1比直接在表格里填數(shù)字更快也不容易漏項(xiàng)。寫(xiě)KMP代碼時(shí)我會(huì)在GetNext和Index_KMP里各加一個(gè)輔助打印函數(shù)輸出每一步的i和j這樣測(cè)試樣例時(shí)能看到匹配過(guò)程不是只有一個(gè)最終結(jié)果。替換和刪除算法中涉及串長(zhǎng)更新的地方我會(huì)用printf打印每次循環(huán)后的串內(nèi)容和長(zhǎng)度一旦結(jié)果不對(duì)馬上能看出是長(zhǎng)度沒(méi)更新還是位置偏移錯(cuò)誤。根據(jù)我個(gè)人經(jīng)驗(yàn)第四章的很多錯(cuò)誤其實(shí)都出在“邊界條件”上而不是算法主體邏輯上。所以每次寫(xiě)完匹配類(lèi)代碼我都會(huì)用三個(gè)測(cè)試用例自測(cè)模式串長(zhǎng)度為1、模式串等于主串、主串為空。這三個(gè)用例能暴露絕大多數(shù)越界和死循環(huán)問(wèn)題省下大量調(diào)試時(shí)間。把這些習(xí)慣保持到考試或項(xiàng)目里串這一章基本就不會(huì)再丟分了。