4.1.1 串：字符构成的有限序列

串是由零个或多个字符组成的有限序列，通常记作 $S{=}^{\prime }{a}_1{a}_2\cdots a_n^{\prime }$。$n$ 是串长；$n=0$ 的串叫空串。空串与只含空格的串不同：后者长度至少为 1，空格也是字符。

子串是主串中连续的一段字符，子序列则可以不连续，本章模式匹配寻找的是子串。子串在主串中的位置通常指首字符位序，位序从 1 开始；程序下标常从 0 开始。串 'ababa' 中模式 'aba' 在位序 1 和 3 各出现一次，这两个出现可以重叠。

基本操作包括赋值、复制、判空、求长、比较、连接、求子串、定位和替换。串比较采用字典序：从左到右找第一对不同字符决定大小；若一个串是另一个的前缀，较短者更小。不能只比较长度，也不能把字符编码相加后比较。

求子串 SubString(S,pos,len) 时，若位序从 1 开始，常见合法条件是 $1\le pos\le |S|$ 且 $0\le len\le |S|-pos+1$；允许长度 0 时结果为空串。接口约定应明确越界如何报告。

手工推演：S='data structure'，空格计入长度。位序 5 是空格，位序 6 开始的长度 9 子串是 'structure'。若直接拿数组下标 6，会从字符 t 开始，产生差一错误。

错解反馈：把空串写成 ' '；把不连续字符选取当子串；认为两个串长度相等就相等，均违背定义。串相等要求长度相同且每一对应字符相同。

迁移题：主串 'aaaa' 中模式 'aa' 有几个允许重叠的出现？答案 3 个，起始位序为 1、2、3。独立验收：能区分空串、空格串、子串、子序列，并对操作写出位序与下标转换。