跳转至

# 字符串基础

## 定义

### 字符集

一个 字符集 Σ Σ 是一个建立了 全序 关系的集合，也就是说，Σ Σ 中的任意两个不同的元素 𝛼 α 和 𝛽 β 都可以比较大小，要么 𝛼 <𝛽 α<β，要么 𝛽 <𝛼 β<α．字符集 Σ Σ 中的元素称为字符．

### 字符串

一个 字符串 𝑆 S 是将 𝑛 n 个字符顺次排列形成的序列，𝑛 n 称为 𝑆 S 的长度，表示为 |𝑆||S|．

如果字符串下标从 1 1 开始计算，𝑆 S 的第 𝑖 i 个字符表示为 𝑆[𝑖]S[i]；

如果字符串下标从 0 0 开始计算，𝑆 S 的第 𝑖 i 个字符表示为 𝑆[𝑖 −1]S[i−1]．

### 子串

字符串 𝑆 S 的 子串 𝑆[𝑖..𝑗]，𝑖 ≤𝑗 S[i..j]，i≤j，表示 𝑆 S 串中从 𝑖 i 到 𝑗 j 这一段，也就是顺次排列 𝑆[𝑖],𝑆[𝑖 +1],…,𝑆[𝑗]S[i],S[i+1],…,S[j] 形成的字符串．

有时也会用 𝑆[𝑖..𝑗]S[i..j]，𝑖 >𝑗 i>j 来表示空串．

### 子序列

字符串 𝑆 S 的 子序列 是从 𝑆 S 中将若干元素提取出来并不改变相对位置形成的序列，即 𝑆[𝑝 1],𝑆[𝑝 2],…,𝑆[𝑝 𝑘]S[p 1],S[p 2],…,S[p k]，1 ≤𝑝 1 <𝑝 2 <⋯ <𝑝 𝑘 ≤|𝑆|1≤p 1<p 2<⋯<p k≤|S|．

### 后缀

后缀 是指从某个位置 𝑖 i 开始到整个串末尾结束的一个特殊子串．字符串 𝑆 S 的从 𝑖 i 开头的后缀表示为 𝑆 𝑢 𝑓 𝑓 𝑖 𝑥(𝑆,𝑖)Suffix(S,i)，也就是 𝑆 𝑢 𝑓 𝑓 𝑖 𝑥(𝑆,𝑖) =𝑆[𝑖..|𝑆| −1]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 结尾的前缀表示为 𝑃 𝑟 𝑒 𝑓 𝑖 𝑥(𝑆,𝑖)Prefix(S,i)，也就是 𝑃 𝑟 𝑒 𝑓 𝑖 𝑥(𝑆,𝑖) =𝑆[0..𝑖]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<a a）．

### 回文串

回文串 是正着写和倒着写相同的字符串，即满足 ∀1 ≤𝑖 ≤|𝑠|,𝑠[𝑖] =𝑠[|𝑠| +1 −𝑖]∀1≤i≤|s|,s[i]=s[|s|+1−i] 的 𝑠 s．

### 汉明距离

汉明距离 是两个等长字符串之间的距离，它表示两个长度相同的字符串对应位字符不同的数量．

我们可以简单的认为对两个串进行异或运算，结果为 1 1 的数量就是两个串的汉明距离．

## 字符串的存储

- 使用 `char` 数组存储，用空字符 `\0` 表示字符串的结尾（C 风格字符串）．
- 使用 C++ 标准库提供的 `string` 类．
- 字符串常量可以用字符串字面量（用双引号括起来的字符串）表示．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, minghu6, NachtgeistW, StudyingFather, countercurrent-time, Enter-tainer, H-J-Granger, ouuan, CCXXXI, mgt, AngelKitty, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Konano, LovelyBuggies, Makkiy, P-Y-Y, PotassiumWings, qinggniq, SamZhangQingChuan, sshwy, Suyun514, Tiphereth-A, weiyong1024, current2020, GavinZhengOI, Gesrua, ghj1222, Great-designer, Haohu Shen, HeRaNO, i-Yirannn, i-yyi, kxccc, lychees, Peanut-Tang, SukkaW, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用