字符串基础

定义

字符集

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

字符串

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

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

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

子串

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

有时也会用 ， 来表示空串。

子序列

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

后缀

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

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

举例来说，字符串 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 类 。
• 字符串常量可以用字符串字面量（用双引号括起来的字符串）表示。

参考资料与注释

• 后缀数组 by. 徐智磊

本页面最近更新： 2024/2/5 15:44:44 ， 更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者： Ir1d , minghu6 , ouuan , qinggniq , CCXXXI , countercurrent-time , Enter-tainer , ghj1222 , Great-designer , Haohu Shen , i-Yirannn , i-yyi , mgt , NachtgeistW , SukkaW , Tiphereth-A , Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用