目录

字符串的比较字符串的字符编码字符串的存储结构字符串的顺序存储结构字符串的链式存储结构不同语言中的字符串C++ STL中的stringstring的构造string迭代器使用string容量操作string增删查改字符串匹配问题单模式串匹配问题多模式串匹配问题

• 字符串名称：字符串定义中的s就是字符串的名称

• 字符串的值： 组成的字符序列就是字符串的值，一般用双引号括起来。

• 字符变量：字符串每一个位置上的元素都是一个字符变量。字符 可以是字母、数字或者其他字符。 是该字符在字符串中的位置。

• 字符串的长度：字符串中字符的数目 称为字符串的长度。

• 空串：零个字符构成的串也成为 「空字符串（Null String）」，它的长度为 ，可以表示为 ""。

• 子串：字符串中任意个连续的字符组成的子序列称为该字符串的 「子串（Substring）」。并且有两种特殊子串，起始于位置为0、长度为k的子串称为 「前缀（Prefix）」。而终止于位置n - 1、长度为k的子串称为 「后缀（Suffix）」。

• 主串：包含子串的字符串相应的称为 「主串」。

• 字符串中的数据元素都是字符，结构相对简单，但规模可能比较庞大。

• 经常需要把字符串作为一个整体来使用和处理。操作对象一般不是某个数据元素，而是一组数据元素（整个字符串或子串）。

• 经常需要考虑多个字符串之间的操作。比如：字符串之间的连接、比较操作。

• 字符串匹配问题。

• 子串相关问题。

• 前缀 / 后缀相关问题；

• 回文串相关问题。

• 子序列相关问题。

字符串的比较

1. 字符串 str1 和字符串 str2 的长度相等。

2. 字符串 str1 和字符串 str2 对应位置上的各个字符都相同。

• 从两个字符串的第 0 个位置开始，依次比较对应位置上的字符编码大小。
• 如果 str1[i] 对应的字符编码等于 str2[i] 对应的字符编码，则比较下一位字符。
• 如果 str1[i] 对应的字符编码小于 str2[i] 对应的字符编码，则说明 str1 < str2，比如："abc" < "acc"
• 如果 str1[i] 对应的字符编码大于 str2[i] 对应的字符编码，则说明 str1 > str2，比如："bcd" > "bad"

• 如果比较到某一个字符串末尾，另一个字符串仍有剩余：
• 如果字符串 str1 的长度小于字符串 str2，即 len(str1) < len(str2)，则 str1 < str2，比如："abc" < "abcde"
• 如果字符串 str1 的长度大于字符串 str2，即 len(str1) > len(str2)，则 str1 > str2，比如："abcde" > "abc"

• 如果两个字符串每一个位置上的字符对应的字符编码都相等，且长度相同，则说明 str1 == str2，比如："abcd" == "abcd"

字符串的字符编码

字符串的存储结构

字符串的顺序存储结构

字符串的链式存储结构

不同语言中的字符串

• C语言中的字符串是使用空字符\0结尾的字符数组。\0符号用于标记字符串的结束。C语言的标准库string.h 头文件中提供了各种操作字符串的函数。

• C++中除了提供 C 风格的字符串，还引入了string类类型。string类处理起字符串来会方便很多，完全可以代替 C 语言中的字符数组或字符串指针。

• Java标准库中也提供了String类作为字符串库。

• Python中使用str对象来代表字符串。str对象一种不可变类型对象。即str类型创建的字符串对象在定义之后，无法更改字符串的长度，也无法改变或删除字符串中的字符

C++ STL中的string

cplusplus.com

https://cplusplus.com/reference/string/string/

string的构造

• string() ：构造空的string类对象，即空字符串

• string(const char* s)：用C格式的string来构造string类对象

• string(size_t n, char c) ：string类对象中包含n个字符c

• string(const string& s) ：拷贝构造函数

string迭代器使用

• iterator ：正向迭代器

• reverse_iterator：反向迭代器

• const_iterator：常量迭代器

• const_reverse_iterator：常量反向迭代器

• begin()返回指向容器中第一个元素的迭代器
end()返回指向容器最后一个元素所在位置后一个位置的迭代器

• cbegin()：在begin()基础上，增加了const属性，不能用于修改元素
cend()：在end()基础上，增加const属性，不能用于修改元素

• rbegin()：反向，返回指向最后一个元素的迭代器
rend() ：反向，返回指向第一个元素所在位置前一个位置的迭代器

• crbegin() ：在rbegin()基础上，增加了const属性，不能用于修改元素
crend() ：在rend()基础上，增加了const属性，不能用于修改元素

string容量操作

string增删查改

字符串匹配问题

单模式串匹配问题

• 基于前缀搜索方法：在搜索窗口内从前向后（沿着文本的正向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共前缀。
著名的Knuth-Morris-Pratt (KMP) 算法和更快的 Shift-Or 算法使用的就是这种方法。

• 基于后缀搜索方法：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共后缀。使用这种搜索算法可以跳过一些文本字符，从而具有亚线性的平均时间复杂度。
最著名的 Boyer-Moore 算法，以及 Horspool 算法、Sunday (Boyer-Moore 算法的简化) 算法都使用了这种方法。

• 基于子串搜索方法：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索满足「既是窗口中文本的后缀，也是模式串的子串」的最长字符串。与后缀搜索方法一样，使用这种搜索方法也具有亚线性的平均时间复杂度。这种方法的主要缺点在于需要识别模式串的所有子串，这是一个非常复杂的问题。
Rabin-Karp 算法、Backward Dawg Matching (BDM) 算法、Backward Nondeterministtic Dawg Matching (BNDM) 算法和 Backward Oracle Matching (BOM) 算法使用的就是这种思想。其中，Rabin-Karp 算法使用了基于散列的子串搜索算法。

多模式串匹配问题

• 基于前缀搜索方法：搜索从前向后（沿着文本的正向）进行，逐个读入文本字符，使用在上构建的自动机进行识别。对于每个文本位置，计算既是已读入文本的后缀，同时也是中某个模式串的前缀的最长字符串。
著名的 Aho-Corasick Automaton (AC 自动机) 算法、Multiple Shift-And 算法使用的这种方法。

• 基于后缀搜索方法：搜索从后向前（沿着文本的反向）进行，搜索模式串的后缀。根据后缀的下一次出现位置来移动当前文本位置。这种方法可以避免读入所有的文本字符。
Commentz-Walter 算法（Boyer-Moore 算法的扩展算法）、Set Horspool 算法（Commentz-Walter 算法的简化算法）、Wu-Manber 算法都使用了这种方法。

• 基于子串搜索方法：搜索从后向前（沿着文本的反向）进行，在模式串的长度为 的前缀中搜索子串，以此决定当前文本位置的移动。这种方法也可以避免读入所有的文本字符。
Multiple BNDM 算法、Set Backward Dawg Matching (SBDM) 算法、Set Backwrad Oracle Matching (SBOM) 算法都使用了这种方法。