字符串基礎概念

• 字符串：簡稱串，是由字符組成的有限序列。串中所包含的字符個數為串長，串長為0的串為空串。串長與所有對應位置字符都相同的串為相等串，空串一定為相等串。
• 子串、子序列：設從原串$S$某一位置開始，若以連續順序取$S$中若干長度的字符，所組成的新串$S^{\prime }$即為$S$的子串，$S$為$S^{\prime }$的主串，不包含$S$本身的子串為真子串；若以不連續順序取$S$中若干長度的字符，所組成的新串$S^{\prime }$即為$S$的子序列
• 前綴、后綴：設從原串$S$的串首開始，若以連續順序取$S$中若干長度的字符，所組成的新串$S^{\prime }$即為$S$的前綴，真前綴是除$S$本身外的所有前綴；設從原串$S$某一位置開始，若以連續順序取$S$中直至末尾的所有字符，所組成的新串$S^{\prime }$即為$S$的后綴，真后綴是指除$S$本身外的所有后綴
• 字典序：比較串間大小關系的方法，按照英文詞典中對單詞排列的順序進行比較，通常基于字符的字母順序或其ASCII碼值
• 回文串：具有鏡像對稱性的字符串，即正序遍歷與倒序遍歷都相等的串。串長為奇數的回文串為奇回文串，其有$1$個中心字符，對稱軸為此中心字符；串長為偶數的回文串為偶回文串，其有$2$個中心字符，對稱軸介于兩中心字符之間。
• 模式匹配：分為單模匹配與多模匹配。設原串$S$、模式串$T$，$T$在$S$中可能多次出現，在$S$中找所有$T$的相等串的過程即為單模匹配；設原串$S$、模式串$\{T_1,?,T_n\}$，在$S$中找到所有$\{T_1,?,T_n\}$的相等串的過程即為多模匹配