此文章僅作為自己學習過程中的記錄和總結，同時會有意地去用英文來做筆記，一些術語的英譯不太準確，內容如有錯漏也請多指教，謝謝！

---

一、串(String)的定義：

• 串(String)：由零個或多個字符組成的有限序列，又名叫字符串。

一般記作 s=“a₁a₂…a_n” (n>=0)，其中s是串的名稱，用雙引號（有些書也用單引號）括起來的字符序列是串的值，注意引號不屬于串的內容。a_i (1<=i<=n)可以是字母、數字或其它字符。 i 就是該字符在串中的位置。串中的字符數目 n 稱為串的長度。

這里解釋幾個概念：

• 空串(null string)：零個字符的串，它的長度為零，可以用兩引號""表示，也可以用希臘字母（空集）表示。
• 空格串：指只包含空格的串，是有內容有長度的，而且可以不只有一個空格。
• 子串與主串：串中任意個數的連續字符組成的子序列稱為該串的子串，相應地，包含子串的串稱為主串。子串在主串中的位置就是子串的第一個字符在主串中的序號。
  (eg: “lover”&“over”, “friend”&“end”, “believe”&“lie”)

---

二、串的比較：

串的比較是通過組成串的字符之間的編碼來進行的，而字符的編碼指的是字符在對應字符集中的序號。

因此，要在C語言中比較兩個串是否相等，必須是它們串的長度以及它們各個對應位置的字符都相等時，才算是相等。即給定 s₁=“a₁a₂…a_n”，s₂=“b₁b₂…b_n”，當且僅當n=m，且a₁=b₁, a₂=b₂, …, a_n=b_n時，才認為s₁=s₂。

對于兩個不相等的串(s₁=“a₁a₂…a_n”, s2=“b₁b₂…b_m”, n !=m)，當滿足以下條件之一時，認為s₁<s₂：

n<m,且a_i=b_i (i=1,2,…,n)。(eg:“hap”&“happy”)。

存在某個k<=min(m,n)，使得a_i=b_i (i=1,2,…,k-1), a_k<b_k。(eg:“happen”&“happy”)。

（應用：電子詞典中查找單詞實現的原理，其實就是字符串這種數據結構的典型應用。）

---

關于上述“對應字符集中的序號”的相關知識：

計算機中的常用字符是使用標準的ASCII編碼，由7位二進制數來表示一個字符，總共可以表示128個字符。后來發現一些特殊符號，128個不夠用，于是擴展ASCII碼由8位二進制數表示一個字符，總共可以表示256個字符。
擴展后的ASCII碼已經足夠滿足以英語為主的語言和特殊符號進行輸入、存儲、輸出等操作的字符需要了。但對于其它語言和文字而言，如中文，256個字符顯然是不夠的。于是后來就有了Unicode編碼，比較常用的是由16位二進制數表示一個字符，這樣就總共可以表示2¹⁶個字符（約為6.5萬多個）。
（為了和ASCII碼兼容，Unicode編碼的前256個字符與ASCII碼完全相同。）

ASCII碼表：
Unicode碼表：

---

三、串的抽象數據類型：

串的邏輯結構和線性表很相似，不同之處在于串針對的是字符集，也就是串中的元素都是字符。
因此，對于串的基本操作與線性表是有很大差別的。線性表更關注的是單個元素的操作，比如查找、插入或刪除一個元素；而串中更多的是查找子串位置、得到指定位置的子串、替換子串等操作。

Data: 串中元素僅由一個字符組成，相鄰元素具有前驅和后驅的關系。

[ADT of strings:]Operations:StrAssign(T, *chars): 生成一個其值等于字符串常量chars的串T。StrCopy(T, S): 串S存在，由串S復制得到串T。ClearString(S): 若串存在，將串清空。StringEmpty(S): 若串S為空，返回true，否則返回false。StrLength(S): 返回串S的元素個數，即串的長度。StrCompare(S, T): 若S>T，返回值>0；若S==T，返回值=0；若S<T，返回值<0。Concat(T, S1, S2): 用T返回由S1和S2連接而成的新串。SubString(Sub, S, pos, len): 串S存在，1<=pos<=StrLength(S)，且0<=len<=StrLength(S)+1-pos。用Sub返回串S的第pos個字符起長度為len的子串。Index(S, T, pos): 串S和T存在，T是非空串，1<=pos<=StrLength(S)。若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現的位置，否則返回0。Replace(S, T, V): 串S，T和V存在，T是非空串。用V替換主串S中出現的所有與T值相等的不重疊的子串。StrInsert(S, pos, T): 串S和T存在，1<=pos<=StrLength(S)+1。在串S的第pos個字符之前插入串T。StrDelete(S, pos, len): 串S存在，1<=pos<=StrLength(S)+1-len。從串S中刪除第pos個字符起長度為len的子串。endADT

---

此處來看一下Index操作的具體實現：

首先，為了示意清楚以及方便，先聲明定義：

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int SElemType; //SElemType的類型根據實際需求而定，此處假設為int。 typedef int Status;/*"Status" is defined as a type of a function, with its returned value representing the result of the function.（Status是函數的類型，它的返回值勢函數結果狀態代碼，0或1.）*/

接下來是Index(S, T, pos)的實現代碼：

[Achieve the operation of "Index".] /*T為非空串。若主串S中第pos個字符之后存在與T相等的子串，則返回第一個這樣的子串在S中的位置，否則返回0。*/ int Index(String S, String T, int pos) {int m, n, i;String sub;if (pos > 0){n = StrLength(S);m = StrLength(T);i = pos;while (i <= n+1-m){SubString(sub, S, i, m); //取主串第i個位置，長度與T相等的子串給sub比較。if (StrCompare(sub, T) != 0){i++;}else{return i;}}}return 0; }

---

四、串的順序存儲結構：

串的順序存儲結構是用一組地址連續的存儲單元來存儲串中的字符序列的。按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區。一般是用定長數組來定義。

既然是定長數組，就存在一個預定義的最大串長度。此處有幾種獲得串長度值的方法：

一般可以將實際的串長度值保存在該定長數組的0下標位置。

有的書中也會定義存儲在數組的最后一個下標位置。

有些編程語言又規定在串值后面加一個不計入串長度的結束標記字符，如’\0’來表示串值的終結。此時若想知道串的長度，則需要遍歷計算了。

不足： 由于是用定長數組來定義串變量，串的順序存儲方式其實是容易出問題的。由于字符串的操作，比如兩串的連接Concat，新串的插入StrInsert，以及字符串的替換Replace，都有可能使得串的長度超過了數組的長度MAXSIZE。

針對這個不足，對于串的順序存儲就有了一些變化。串值的存儲空間可在程序執行過程中動態分配而得。比如在計算機中存在一個自由存儲區，叫做 “堆”。這個堆可以由C語言的動態分配函數 malloc() 和 free() 來管理。

---

五、串的鏈式存儲結構：

對于串的鏈式存儲結構，與線性表是相似的。但是由于串結構的特殊性（結構中的每個元素數據是一個字符），如果也簡單的應用鏈表存儲串值，即一個結點對應一個字符，就會造成很大的空間浪費。因此，一個結點可以存放一個字符，也可以考慮存放多個字符。最后一個結點若是未被占滿時，可以用"#"或其他非串值字符補全，如圖所示。

當然，此處一個結點存放多少個字符才合適就變得更重要了。這會直接影響著串處理的效率，需要根據實際情況做出選擇。

但是串的鏈式存儲結構除了在連接串與串的操作上有一定方便，總的來說還是不如順序存儲結構靈活，性能也不如順序存儲結構，因此我們也不過多討論了。

---

（注：“六、BF算法（樸素的模式匹配算法）” 及 “七、KMP模式匹配算法” 部分內容引用自用戶@Sirim233333的帖子（算法）通俗易懂的字符串匹配KMP算法及求next值算法，只做筆記用，若有不妥立刻刪除，感謝！）

---

六、BF算法（樸素的模式匹配算法）：

• BF算法：即暴力(Brute Force)算法，是普通的模式匹配算法，是一種蠻力算法。

BF算法的思想：
將主串S的第一個字符與模式串T的第一個字符進行匹配。若相等，則繼續比較主串S的第二個字符和模式串T的第二個字符；若不相等，則比較主串S的第二個字符和模式串T的第一個字符，依次比較下去，直到得出最后的匹配結果。
即：首先S[1]和T[1]比較，若相等，則再比較S[2]和T[2]，一直到T[M]為止；若S[1]和T[1]不等，則S向右移動一個字符的位置，再依次進行比較。已知n為主串長度，m為模式串長度。如果存在k (1≤k≤n)且S[k+1…k+m]=T[1…m]，則匹配成功；否則失敗。

若令n為主串長度，m為模式串長度，則該算法最壞情況下要進行 m * (n-m+1) 次比較，時間復雜度為 O(m*n) 。

---

在串的操作中，有BF算法的很典型的體現：對子串的定位操作。

對子串的定位操作通常稱作 “串的模式匹配”，是串操作中最重要的操作之一。
思路簡單來說就是：對主串的每一個字符作為子串的開頭，與模式串進行匹配。對主串做大循環，每個字符開頭做模式串T的長度的小循環，直到匹配成功或者全部遍歷完成為止。

上面已通過使用串的其他操作來實現模式匹配的算法Index，現在只用基本的數組來實現同樣的算法。
假設主串S和模式串T的長度存在S[0]和T[0]中。 實現代碼如下：

[Achieve the operation of "Index" with BF algorithm.] /*返回模式串T在主串S中第pos個字符之后的位置。若不存在，則函數返回值為0。*/ /*串T非空，1<=pos<=StrLength(S)。*/ int Index(String S, String T, int pos) {int i, j;i = pos; //i表示主串S中當前位置下標。若pos不為1，則從pos位置開始匹配。j = 1; //j表示模式串T中當前位置的下標值。初始化為1，即從頭開始。while (i <= S[0] && j <= T[0]) //若i小于主串S長度，且j小于串T的長度時循環。{if (S[i] == T[i]){i++;j++;}else //指針后退，重新開始匹配。{i = i - j + 2; //i退回到上次匹配首位的下一位。j = 1; //j退回到串T的首位。}}if (j > T[0]) //j大于串T長度代表匹配成功。{return i - T[0]; //此時i處于串T末位的下一位，因此要減去一個串T長度。}else{return 0;} } T(n)=O(m*n)

---

總的來說，BF算法，即樸素模式匹配算法，正如其名Brutal Force，是一種很低效的蠻力算法。很多年前，科學家們認為這種有多個0和1重復字符的字符串，模式匹配需要挨個遍歷的算法是非常糟糕的。

于是有三位前輩，D.E.Knuth, J.H.Morris, V.R.Pratt 發表了一個模式匹配算法，可以大大避免重復遍歷的情況，我們稱之為Knuth-Morris-Pratt算法，簡稱KMP算法。

---

七、KMP模式匹配算法：

由前面所說，樸素算法思路簡單暴力，但兩個串都需要依次重復遍歷，算法的時間復雜度為O(n*m)，效率很低。科學家們為了提高效率，發表了一種可以避免重復遍歷的算法，我們稱之為KMP算法。

一般地，在匹配中，我們是不知道主串的內容的，而模式串是我們自己定義的。
樸素算法中，模式串P的第 j 位失配，我們處理的方法是默認的把串P后移一位。
但我們知道，在前一輪的比較中，串P的前 (j-1) 位與主串S中間對應的某 (j-1) 個元素已經匹配成功了。這就意味著，在一輪的匹配中，我們知道了主串S的部分內容。因此，我們可以利用這些內容，讓P多移幾位，減少遍歷的次數，而非無腦暴力地依次重復遍歷。

樸素算法與kmp算法的比較：

• 樸素算法： 每次失配，S串的索引i定位的本次嘗試匹配的第一個字符的后一個。P串的索引j定位到1；T(n)=O(n*m)。
• KMP算法： 每次失配，S串的索引i不動，P串的索引j定位到某個數。T(n)=O(n+m)，時間效率明顯提高。

注意，此處的“定位到某個數”，就是接下來要引入的next值，其數值實際上就是P往后移的位數。

---

此處舉一個例子：

• ① 例如，Pj處失配（圖中綠色的是Pj），則我們可以確定P1…Pj-1是與Si…Si+j-2相匹配的位置，即它們是對應相等的。
  

• ② 假設P₁…P_j-1中，P₁…P_k-1 (1<k<j)與P_j-k+1…P_j-1 是對應相等的。為了下面說的清楚，我們把這種關系叫做 “首尾重合”。于是我們可以推出，P₁…P_k-1 與S_i…S_i+j-2。
  （我們可以發現，后面一段P_j-k+1…P_j-1 的開頭位置是P_j-k+1，結束位置是P_j-1，由j-k+1=j-(k-1)可知，此段的長度與前面一段是相同的。這也是為何我們稱之為“首尾重合“。）
  

• ③ 接下來要做的就是把模式串右移。
  

• ④ 為了表示下一輪匹配時 j定位的地方，我們將其定義為數組next[j]，而next[j]的數值就是第j個元素前 j-1個元素首尾重合部分個數加1。（我們可以這樣理解：j值的多少取決于當前字符之前的串的前后綴的相似度。）當然，為了能遍歷完整，首尾重合部分的元素個數應取到最多，即next[j]應取盡量大的值。
  "前綴"指除了最后一個字符以外，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外，一個字符串的全部尾部組合。以”ABCDABD”為例，進行介紹：
  ”A”的前綴和后綴都為空集，共有元素的長度為0；
  ”AB”的前綴為[A]，后綴為[B]，共有元素的長度為0；
  ”ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度0；
  ”ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為0；
  ”ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，長度為1；
  ”ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，長度為2；
  ”ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。

• ⑤ 最后，如果我們知道了一個字符串的next值，那么KMP算法也就很好懂了。相比樸素算法，當發生失配時，i不變，j=next[j]就好了。接下來就是怎么確定next值了。

---

八、KMP算法 – next數組的簡單計算：

我們規定任何一個串，next[1]=0。（next[1]在kmp算法中不會用到）

此處舉一個簡單例子來演示推導next數組的過程：

總結之后，我們可以得到一個十分重要的公式：

---

九、KMP算法 – 求next數組的算法：

void get_next(String T, int* next) {int i, j;i = 1;j = 0;next[1] = 0;while (i < T[0]) //T[0]存放著模式串T的長度。{if (j == 0 || T[i] == T[j]) //T[i]表示后綴的單個字符，T[j]表示前綴的單個字符。{i++;j++;if (T[i] != T[j]) //若當前字符與前綴字符不同。{next[i] = j; //則當前的j為next在i位置的值。}else{next[i] = next[j]; //若與前綴字符相同，則將前綴字符的next值賦next在i位置的值。}}else{j = next[j]; //若字符不相同，則j回溯。}} } T(n)=O(n+m)

總結

以上是生活随笔為你收集整理的串--串的定义，顺序、链式存储结构，BF、KMP模式匹配算法（C语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。