字符串基础

定义

字符集

一个 字符集 是一个建立了全序关系的集合,也就是说, 中的任意两个不同的元素 都可以比较大小,要么 ,要么 。字符集 中的元素称为字符。

字符串

一个 字符串 是将 个字符顺次排列形成的序列, 称为 的长度,表示为

如果字符串下标从 开始计算, 的第 个字符表示为

如果字符串下标从 开始计算, 的第 个字符表示为

子串

字符串 子串 ,表示 串中从 这一段,也就是顺次排列 形成的字符串。

有时也会用 来表示空串。

子序列

字符串 子序列 是从 中将若干元素提取出来并不改变相对位置形成的序列,即

后缀

后缀 是指从某个位置 开始到整个串末尾结束的一个特殊子串。字符串 的从 开头的后缀表示为 ,也就是

真后缀 指除了 本身的 的后缀。

举例来说,字符串 abcabcd 的所有后缀为 {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd},而它的真后缀为 {d, cd, bcd, abcd, cabcd, bcabcd}

前缀

前缀 是指从串首开始到某个位置 结束的一个特殊子串。字符串 的以 结尾的前缀表示为 ,也就是

真前缀 指除了 本身的 的前缀。

举例来说,字符串 abcabcd 的所有前缀为 {a, ab, abc, abca, abcab, abcabc, abcabcd}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabc}

字典序

以第 个字符作为第 关键字进行大小比较,空字符小于字符集内任何字符(即:)。

回文串

回文串 是正着写和倒着写相同的字符串,即满足

字符串的存储

  • 使用 char 数组存储,用空字符 \0 表示字符串的结尾(C 风格字符串)。
  • 使用 C++ 标准库提供的 string
  • 字符串常量可以用字符串字面量(用双引号括起来的字符串)表示。

参考资料与注释


评论