字符串基礎
定義
字符集
一個 字符集 \(\Sigma\) 是一個建立了 全序 關係的集合，也就是説，\(\Sigma\) 中的任意兩個不同的元素 \(\alpha\) 和 \(\beta\) 都可以比較大小，要麼 \(\alpha<\beta\)，要麼 \(\beta<\alpha\)。字符集 \(\Sigma\) 中的元素稱為字符。
字符串
一個 字符串 \(S\) 是將 \(n\) 個字符順次排列形成的序列，\(n\) 稱為 \(S\) 的長度，表示為 \(|S|\)。
如果字符串下標從 \(1\) 開始計算，\(S\) 的第 \(i\) 個字符表示為 \(S[i]\)；
如果字符串下標從 \(0\) 開始計算，\(S\) 的第 \(i\) 個字符表示為 \(S[i-1]\)。
子串
字符串 \(S\) 的 子串 \(S[i..j]，i≤j\)，表示 \(S\) 串中從 \(i\) 到 \(j\) 這一段，也就是順次排列 \(S[i],S[i+1],\ldots,S[j]\) 形成的字符串。
有時也會用 \(S[i..j]\)，\(i>j\) 來表示空串。
子序列
字符串 \(S\) 的 子序列 是從 \(S\) 中將若干元素提取出來並不改變相對位置形成的序列，即 \(S[p_1],S[p_2],\ldots,S[p_k]\)，\(1\le p_1< p_2<\cdots< p_k\le|S|\)。
後綴
後綴 是指從某個位置 \(i\) 開始到整個串末尾結束的一個特殊子串。字符串 \(S\) 的從 \(i\) 開頭的後綴表示為 \(\textit{Suffix(S,i)}\)，也就是 \(\textit{Suffix(S,i)}=S[i..|S|-1]\)。
真後綴 指除了 \(S\) 本身的 \(S\) 的後綴。
舉例來説，字符串 abcabcd 的所有後綴為 {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd}，而它的真後綴為 {d, cd, bcd, abcd, cabcd, bcabcd}。
前綴
前綴 是指從串首開始到某個位置 \(i\) 結束的一個特殊子串。字符串 \(S\) 的以 \(i\) 結尾的前綴表示為 \(\textit{Prefix(S,i)}\)，也就是 \(\textit{Prefix(S,i)}=S[0..i]\)。
真前綴 指除了 \(S\) 本身的 \(S\) 的前綴。
舉例來説，字符串 abcabcd 的所有前綴為 {a, ab, abc, abca, abcab, abcabc, abcabcd}, 而它的真前綴為 {a, ab, abc, abca, abcab, abcabc}。
字典序
以第 \(i\) 個字符作為第 \(i\) 關鍵字進行大小比較，空字符小於字符集內任何字符（即：\(a< aa\)）。
迴文串
迴文串 是正着寫和倒着寫相同的字符串，即滿足 \(\forall 1\le i\le|s|, s[i]=s[|s|+1-i]\) 的 \(s\)。
字符串的存儲
- 使用
char數組存儲，用空字符\0表示字符串的結尾（C 風格字符串）。 - 使用 C++ 標準庫提供的
string類。 - 字符串常量可以用字符串字面量（用雙引號括起來的字符串）表示。
參考資料與註釋
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, ouuan, qinggniq, i-Yirannn, minghu6
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用