🔥前言

今天補(bǔ)充數(shù)據(jù)結(jié)構(gòu)專欄的文章，前陣子一直在準(zhǔn)備考研，期間也是復(fù)習(xí)了很長時(shí)間的數(shù)據(jù)結(jié)構(gòu)知識(shí)，對(duì)于一些結(jié)構(gòu)也有了更深刻和獨(dú)特的理解。今天就把有關(guān) “串” 的基本操作以及比較熱門的KMP 算法做一個(gè)系統(tǒng)的總結(jié)，后期也會(huì)更新樹、圖以及考研熱門算法的文章，建議大家訂閱學(xué)習(xí)。

串的基礎(chǔ)知識(shí)

先了解有關(guān)串的一些知識(shí)，方便以后遇到某些術(shù)語時(shí)能夠心領(lǐng)神會(huì)。

串的定義：
串，即字符串（String）是由零個(gè)或多個(gè)字符組成的有限序列，串中的字符個(gè)數(shù)n稱為串的長度。n = 0 時(shí)的串稱為空串

串的術(shù)語：
子串：串中任意個(gè)連續(xù)的字符組成的子序列。
主串：包含子串的串。
字符在主串中的位置： 字符在串中的序號(hào)。
子串在主串中的位置：子串的第一個(gè)字符在主串的位置

比如：
S = ‘iPhone 11 Pro Max?’
‘iPhone’ 和 'Pro M' 都是串 S 的子串，S 是子串‘iPhone’ 的主串
'1' 在S 中的位置是8(第一次出現(xiàn)，下標(biāo)從1開始計(jì)算)

字符集編碼：每個(gè)字符在計(jì)算機(jī)中對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，比較字符的大小其實(shí)就是比較二進(jìn)制數(shù)的大小，這點(diǎn)在后續(xù)的字符串比較方法中會(huì)有體現(xiàn)。

串的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)

采用靜態(tài)數(shù)組實(shí)現(xiàn)（定長順序存儲(chǔ)）：

#define MAXLEN 255 //預(yù)定義最大串長為255
typedef struct{char ch[MAXLEN];	// 每個(gè)分量存儲(chǔ)一個(gè)字符int length;		// 串的實(shí)際長度
}SString;

采用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)（堆分配存儲(chǔ)）：

typedef struct {char* ch;int length;
}HString;// 初始化操作
HString S;
S.ch = (char*)malloc(MAXLEN * sizeof(char)); // 使用堆分配，使用過后需要手動(dòng) free 掉
S.length = 0;

在我們自己定義串的時(shí)候可以在 ch[0] 的位置存儲(chǔ)串的長度，這樣可以使字符的位序和數(shù)組的下標(biāo)相同，但是要注意此時(shí)的長度取值范圍僅在0~255之內(nèi)，這是 char 類型能存儲(chǔ)的最大長度。

鏈?zhǔn)酱鎯?chǔ)

鏈?zhǔn)酱鎯?chǔ)的形式一般都與單鏈表的存儲(chǔ)形式一致，所以牢固掌握單鏈表很重要，有關(guān)文章在此專欄也有提供。

typedef struct StringNode {char ch; // 每個(gè)結(jié)點(diǎn)存一個(gè)字符struct StringNode* next;
}StringNode, *String;

如果每個(gè)結(jié)點(diǎn)只能存儲(chǔ)一個(gè)字符，這樣的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)密度就太低了，因?yàn)?32 位操作系統(tǒng)下指針的大小為 4 個(gè)字節(jié)。因此可以適當(dāng)?shù)奶岣呙總€(gè)結(jié)點(diǎn)的存儲(chǔ)容量，如：

typedef struct StringNode {char ch[8]; // 每個(gè)結(jié)點(diǎn)存多個(gè)字符struct StringNode* next;
}StringNode, *String;

順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)可以參考鏈表和順序表的優(yōu)缺點(diǎn)，從增刪改查的效率上考慮即可。

基本操作的實(shí)現(xiàn)

這里采用順序存儲(chǔ)的方式來實(shí)現(xiàn)基本操作，即：

#define MAXLEN 255
typedef struct {char ch[MAXLEN];int length;
}SString;

另外，舍棄ch[0]，從下標(biāo) 1 開始存儲(chǔ)字符。

求子串

對(duì)應(yīng)方法：SubString(&Sub,S,pos,len)：用Sub 返回串 S 的第pos 個(gè)字符起長度為 len 的子串

具體實(shí)現(xiàn)：

bool SubString(SString& Sub, SString S, int pos, int len) {if (pos + len - 1 > S.length) // 子串越界return false;for (int i = pos; i < pos + len; i++) {Sub.ch[i - pos + 1] = S.ch[i]; // 左邊從下標(biāo) 1 開始賦值}Sub.length = len;return true;
}

字符串比較

對(duì)應(yīng)方法：StrCompare(S,T)：若S>T，則返回值>0；若S=T，返回值=0，若小于，則返回值<0

具體實(shí)現(xiàn)：

int StrCompare(SString S, SString T) {for (int i = 1; i <= S.length && i <= T.length; i++) {if (S.ch[i] != T.ch[i]) // 如果不相等，直接用減法的結(jié)果當(dāng)成比較結(jié)果return S.ch[i] - T.ch[i];}return S.length - T.length; // 此時(shí)比較字符串長度，用減法結(jié)果表示即可
}

返回子串位置

對(duì)應(yīng)方法：Index(S,T)：若主串S中存在與串T值相同的子串則返回他在主串中第一次出現(xiàn)的位置，否則返回0。

具體實(shí)現(xiàn)：

int Index(SString S, SString T) {SString P;for (int i = 1; i <= S.length - T.length + 1; i++) {SubString(P, S, i, T.length);if (StrCompare(P, T) == 0) {return i;}}return 0;
}

這里稍微的“偷懶”了一下，但是代碼邏輯很清晰：

• P 串是主串 S 中長度為 T串長度的子串，賦值方法當(dāng)然是通過調(diào)用之前寫的獲取子串方法
• 循環(huán)中 i 沒必要走到主串的長度，只要 i 加上 T 的子串長度不大于 主串即可
• 調(diào)用字符串比較函數(shù)，只要P 與 T 相等，返回 i 值就是子串在主串中第一次出現(xiàn)的位置

字符串模式匹配

定義：在主串中找到與模式串相同的子串，并返回其所在位置。
兩種算法：樸素模式匹配 與 KMP 算法

樸素模式匹配算法

這種方式可以稱之為暴力解法：

• 我們從主串開始遍歷，如果位序 1 不匹配，那么從2開始匹配；如果位序1至3都匹配，位序4不匹配，那么主串還是要從位序2繼續(xù)匹配，而模式串回到位序1
• 因此每次的模式串都要從位序1遍歷，而主串的位序會(huì)比上一次的位序多1
• 只要處理好主串的位序問題，那么就能暴力解題

具體算法：

int commonCompare(SString &s1, SString &s2) {int i,j;for (i = 1, j = 1; i <= s1.length,j <= s2.length;) {if (s1.ch[i] == s2.ch[j]) {i++, j++;}else {i = i - j + 2; // 理解此行代碼很重要，此寫法可以讓位序逐漸加 1 j = 1;}if (j > s2.length)return i - s2.length;}return 0;
}

KMP 算法

KMP 算法比起樸素匹配算法多了一個(gè)重要的 next 數(shù)組，而且該數(shù)組與主串沒有任何關(guān)系，我們需要通過模式串來求出 next 數(shù)組作為模式串指針指向的重要依據(jù)，而且主串的指針不回溯。

圖示：

這里我們可以明顯看到前四個(gè)字符都是匹配的，如果按照樸素模式匹配算法的邏輯，下一次主串指針會(huì)指向2，模式串指向1，重復(fù)樸素模式匹配操作；但實(shí)際上我們是可以知道主串前四個(gè)字符與模式串是對(duì)應(yīng)的，因此不必讓模式串指向1，而是將模式串向右 “移動(dòng)”，如果模式串指向3，那說明前兩個(gè)字符為a、b，這與主串a(chǎn)、a，并不對(duì)應(yīng)，因此可以讓模式串指向2，a 與 a 是對(duì)應(yīng)的，那么下一步就是比較 b 與主串的第五個(gè)字符，時(shí)間效率提高了不少。

具體算法實(shí)現(xiàn)：

int Index_kmp(SString& S, SString& T, int next[]) {int i = 1, j = 1;while (i <= S.length && j <= T.length) {if (S.data[i] == T.data[j] || j == 0) {i++;j++;}else {j = next[j]; // 模式串的指向改變}if (j > T.length) {return i - T.length;}elsereturn 0;}
}

求 next 數(shù)組(手算)

上面也提到 next 數(shù)組是KMP 算法中的核心，因此一定要會(huì)手算該數(shù)組，其代表的也是當(dāng)模式串在 j 位置不匹配時(shí)，下一步應(yīng)該指向的位置：j = next[j]。以下圖為例：

如果第一個(gè)位置就不匹配，那就讓 next[j] 的值為0，在寫算法時(shí)如果 j 為0，那就讓主串和模式串的指針都加1 即可；如果第二個(gè)位置不匹配，直接讓 next[j] 為1，也就是讓模式串的第一個(gè)和主串的第二個(gè)字符比較。以后寫 next 數(shù)組時(shí)，指針1和2的位置分別無腦寫0和1。

對(duì)于此例也是一樣，現(xiàn)在看位序3失配時(shí)，next 該為多少：
主串與模式串前兩個(gè)字符都是 a和b，顯然模式串右移一位后a與b并不匹配，因此位序3的next 應(yīng)為 1。

對(duì)于位序4：
前三個(gè)字符均為aba，因此模式串移動(dòng)兩位后的 a 可以與主串第三位對(duì)應(yīng)，所以位序4的next應(yīng)為2。

對(duì)于位序5：
右移兩位后雖然 a 與 a 對(duì)應(yīng)，但是隨后的 b 與 a 不對(duì)應(yīng)，所以其next 還是 2。

對(duì)于位序6：
模式串的 ab 與 主串的 ab 對(duì)應(yīng)，因此其 next 為3。

即 next[7] = { ,0,1,1,2,2,3}，next[0]舍棄不用。

next 數(shù)組優(yōu)化為nextVal

KMP 算法的優(yōu)化實(shí)際上也就是對(duì)next 數(shù)組的優(yōu)化，優(yōu)化思路如下：

比如第三個(gè)位序不匹配時(shí)，我們除了知道兩者的前兩個(gè)字符為 ab 外，其次可以知道主串的第三字符一定不是 a，那么模式串的第一個(gè)字符 a 就沒必要再去和主串的第三個(gè)字符比較了，直接讓 next 的值為0，下一步主串和模式串的指針都加1。

其余位序也是以同樣的思維得到，我算出的數(shù)組為：
nextVal[7] = { ,0,1,0,2,1,3}

給出對(duì)應(yīng)的轉(zhuǎn)換函數(shù)：

// 優(yōu)化 next 為 nextVal
void optimize_next(int next[],int nextVal[],SString &T) {nextVal[1] = 0; // 無腦寫0for (int j = 2; j <= T.length; j++) {// 字符相等，nextVal 的值應(yīng)為前面字符對(duì)應(yīng)的nextValif (T.ch[j] == T.ch[next[j]]) {nextVal[j] = nextVal[next[j]];}else {// 字符不等，無法優(yōu)化，繼承next數(shù)組的數(shù)據(jù)即可nextVal[j] = next[j];}}
}

那么到此 串 的知識(shí)、基本操作的實(shí)現(xiàn)、樸素匹配和KMP算法以及優(yōu)化就總結(jié)完畢了，重點(diǎn)是掌握KMP算法中的手算 next 數(shù)組，大家可以自己找主串和模式串進(jìn)行練習(xí)，徹底掌握 KMP 算法。