一、串的基本概念

串是由零個或多個字元組成的有限序列。記作str="a0a1…an-1"（n≥0）。

串中所包含的字元個數n稱為串長度，當n=0時，稱為空串。

一個串中任意連續的字元組成的子序列稱為該串的子串。

包含子串的串相應地稱為主串。

若兩個串的長度相等且對應字元都相等，則稱兩個串相等。

設s是一個長度為n的串，其中的字元各不相同，則s中的所有子串個數是多少？

二、串的抽象資料型別

三、串的儲存結構

串的順序儲存結構—順序

和順序表一樣，用一個data陣列和一個整型變數size來表示一個順序串，size表示data陣列中實際字元的個數。

為了簡單，data陣列採用固定容量為MaxSize（可以模仿順序表改為動態容量方式）。

順序串類SqString

順序串上的基本運算演算法設計與順序表類似，僅以求子串為例說明。

求子串：對於一個順序串求序號i開始長度為j的子串。

實現：先建立一個空串s，當引數正確時，s子串的字元序列為data[i..i+j-1]，共j個字元，當i和i+j-1不在有效序序號0～size-1範圍內時，則引數錯誤，此時返回空串。

設計一個演算法Strcmp(s，t)，以字典順序比較兩個英文字母串s和t的大小，假設兩個串均以順序串儲存。

串的鏈式儲存結構—鏈串

用帶頭結點的單鏈表表示鏈串

例如，s= "ABCDEFGHIJKLMN"，共14個字元。

鏈串的結點型別LinkNode（結點大小為1）

一個鏈串用一個頭結點head來唯一標識，鏈串類LinkString

鏈串上的基本運算演算法設計與單鏈表類似，僅以串插入演算法為例說明。

串插入：鏈串在序號i位置插入串t

實現：先建立一個空串s，當引數正確時，採用尾插法建立結果串s：

（1）將當前鏈串的前i個結點複製到s中。

（2）將t中所有結點複製到s中。

（3）再將當前串的餘下結點複製到s中。

串的模式匹配

設有兩個串s和t，串t定位操作就是在串s中查詢與子串t相等的子串。

通常把串s稱為目標串，把串t稱為模式串，因此定位也稱作模式匹配。

模式匹配成功是指在目標串s中找到一個模式串t。

不成功則指目標串s中不存在模式串t。

BF演算法

思路：目標串s="s0s1…sn-1"，模式串t="t0t1…tm-1"

第1趟：從s0/t0開始比較，若相等，則繼續逐個比較後續字元。如果對應的字元全部相同且t的字元比較完，說明t是s的子串，返回t在s中的起始位置，表示匹配成功；如果對應的字元不相同，說明第一趟匹配失敗。

第2趟：從s1/t0開始比較，若相等，則繼續逐個比較後續字元。如果對應的字元全部相同且t的字元比較完，說明t是s的子串，返回t在s中的起始位置，表示匹配成功；如果對應的字元不相同，說明第一趟匹配失敗。

依次類推。只要有一趟匹配成功，則說明t是s的子串，返回t在s中的起始位置。如果i超界都沒有匹配成功，說明t不是s的子串，返回-1。

BF演算法效能

該演算法在最好情況下的時間複雜度為O(m)，即主串的前m個字元正好等於模式串的m個字元。

最壞情況下的時間複雜度為O(n×m)。

平均情況下的時間複雜度為O(n×m)。

KMP演算法

主要是消除了目標串指標的回溯，從而使演算法效率有了某種程度的提高。

KMP演算法效能

設目標串s的長度為n，模式串t長度為m。

在KMP演算法中求next陣列的時間複雜度為O(m)。

在後面的匹配中因主串s的下標i不減即不回溯，比較次數可記為n。

KMP演算法總的時間複雜度為O(n+m)。

例子：設目標串s="ababcabcacbab"，模式串t="abcac"。給出KMP進行模式匹配的過程。

KMP演算法的效能提高了嗎？

KMP演算法跳過了中間一些趟，正確嗎？

例子：設s="aaabaaaab"，t="aaaab"。計算模式串t的nextval函式值。並畫出利用改進KMP演算法進行模式匹配時每一趟的匹配過程。

例子：設目標串為s="abcaabbabcabaacbacba"，模式串t="abcabaa"。計算模式串t的nextval函式值。並畫出利用KMP演算法進行模式匹配時每一趟的匹配過程。