Chapter 04 字符串
1. 基本概念¶
字符串: 由0或多个字符顺序排列所组成的有限序列，称“串”
串长度：字符串所包含的字符个数
空串：长度为零的串“”；
空格串：“ ”
字符串常数：用一对双撇号“xxxx”作为左右括号，中间字符个数有限, 如“SUNDAY”,“123”，“字符串”等.
为了字符串间比较和运算的便利，字符编码表一般遵循“偏序编码规则”。
字符偏序：根据字符的自然含义，某些字符间两两可以比较次序。大多情况下是字典序.
子串: 若 \(s_2\) 出现在 \(s_1\) 中, 则称 \(s_2\) 是 \(s_1\) 的子串, 或 \(s_1\) 包含 \(s_2\)
真子串: 非空且不为自身的子串
2. 字符串的存储结构与实现¶
静态存储
- 顺序存储
- C++标准串的运算实现 （即C风格的字符串）
动态存储
- String类的运算实现
2.1 顺序存储¶
标准字符串：将C++的
采用 char S[M] 的形式定义字符串变量
M 是常量，保持不变
串的结束标记：'\0'
因此, 长度为M的字符串实际最大容量的为(M-1)
Warning
对于两个字符串 char s1[7]="hello", char s2[3]="aa". 不能直接执行 s1=s2 将 s2 复制给 s1, 这是因为 s1, s2 是字符数组的常量指针, 指向数组首地址, 不可被更改. 复制可以使用 strcpy 函数.
3. 字符串模式匹配¶
用给定的模板P，在目标字符串T中搜索与模板P全相同的一个子串，并返回 P 和 T 匹配的第一个子串的首字符位置
举例:
T＝“e==asdk==nje==asdk==”，P=“asdk”
返回1
优化后的 next 数组:
本质上就是如果当前位置失配而要跳转到的位置与当前位置相同, 那么它也一定会失配, 所以可以多跳一步.