《大話資料結構》配套原始碼：串（Python版）

該書隨書原始碼的語言為C；我參考書中內容和配套原始碼，寫了一套Python格式的配套原始碼。這套配套原始碼並非直接翻譯C語言的配套原始碼，而是結合我的理解略作了修改。

串的抽象資料型別

def str_assign（chars： List［str］）：     “”“生成一個其值等於字串常量chars的串”“”     return “”。join（chars）  ​ def str_copy（s： str）：     “”“由串s複製得串t”“”     return copy。deepcopy（s） ​ ​ def string_empty（s： str）：     “”“若串s為空，則返回True，否則返回False”“”     return not s ​ ​ def str_length（s： str）：     “”“返回串s的元素個數，即串的長度”“”     return len（s） ​ ​ def concat（s1： str， s2： str）：     “”“返回s1和s2聯接而成的新串”“”     return s1 + s2 ​ ​ def sub_string（s： str， pos： int， length： int）：     “”“返回串s的第pos個字元起長度為length的子串”“”     if 0 <= pos <= pos + length <= len（s）：         return s［pos： length］ ​ ​ def index（s： str， t： str， pos）：     “”“若主串s中存在和串t值相同的子串，則返回它在主串s中第pos個字元之後第一次出現的位置，否則返回0”“”     if 0 <= pos < len（s）：         if t in s［pos：］：             return s［pos：］。index（t）     return 0 ​ ​ def replace（s： str， t： str， v： str）：     “”“用V替換主串s中出現的所有與t相等的不重疊的子串”“”     return s。replace（t， v） ​ ​ def str_insert（s： str， pos： int， t： str）：     “”“在串s的第pos個字元之前插入串t”“”     if 0 <= pos <= len（s）：         return s［：pos］ + t + s［pos：］ ​ ​ def str_delete（s： str， pos： int， length： int）：     “”“在傳s中刪除第pos個字元起長度為length的子串”“”     if 0 <= pos <= pos + length <= len（s）：         return s［：pos］ + s［pos + length：］

樸素的模式匹配演算法

時間複雜度：O（N×M），其中N為字串s的長度，M為字串t的長度

def index_simple（s： str， t： str， pos： int）：     “”“樸素的模式匹配演算法”“”     i = pos  # i用於主串s中當前位置下標，若pos不為1則從pos位置開始匹配     j = 0  # j用於子串t中當前位置下標值     while i < len（s） and j < len（t）：         if s［i］ == t［j］：             i += 1             j += 1         else：             i = i - j + 1             j = 0     if j >= len（t）：         return i - len（t）     else：         return -1 ​ ​ def index_simple_2（s： str， t： str， pos： int）：     “”“樸素的模式匹配演算法”“”     while pos + len（t） <= len（s）：         if s［pos：pos + len（t）］ == t：             return pos         pos += 1     else：         return -1

KMP模式匹配演算法

時間複雜度：O（N+M），其中N為字串s的長度，M為字串t的長度

def get_next（t）：     “”“透過計算返回子串t的next陣列”“”     i = 0     j = -1     next = ［-1］ * len（t）     while i < len（t） - 1：         if j == -1 or t［i］ == t［j］：             i += 1             j += 1             next［i］ = j         else：             j = next［j］  # 若字元不相同，則j值回溯     return next ​ ​ def index_kmp（s： str， t： str， pos： int）：     “”“KMP模式匹配演算法”“”     i = pos  # i用於主串s中當前位置下標，若pos不為1則從pos位置開始匹配     j = 0  # j用於子串t中當前位置下標值     next = get_next（t）     while i < len（s） and j < len（t）：         if j == -1 or s［i］ == t［j］：             i += 1             j += 1         else：             j = next［j］     if j >= len（t）：         return i - len（t）     else：         return -1 ​ ​ def get_next_val（t）：     “”“透過計算返回子串t的next陣列（改進演算法）”“”     i = 0     j = -1     next = ［-1］ * len（t）     while i < len（t） - 1：         if j == -1 or t［i］ == t［j］：             i += 1             j += 1             if t［i］ ！= t［j］：                 next［i］ = j             else：                 next［i］ = next［j］         else：             j = next［j］  # 若字元不相同，則j值回溯     return next ​ ​ def index_kmp_mend（s： str， t： str， pos： int）：     “”“KMP模式匹配演算法（改進演算法）”“”     i = pos  # i用於主串s中當前位置下標，若pos不為1則從pos位置開始匹配     j = 0  # j用於子串t中當前位置下標值     next = get_next_val（t）     while i < len（s） and j < len（t）：         if j == -1 or s［i］ == t［j］：             i += 1             j += 1         else：             j = next［j］     if j >= len（t）：         return i - len（t）     else：         return -1