子串

子串
术语名称	子串
英语名称	substring
别名	子字符串, subword, factor

真子串
术语名称	真子串
英语名称	proper substring
别名	真子字符串

子串(substring)指两个字符串中一个字符串是另一个字符串的一部分，或者说，一个字符串是另一个字符串中连续字符组成的部分，一个字符串与其他字符串的连接结果是另一个字符串。 取给定字符串指定下标子串的运算也称为字符串的子串运算。

定义

子串
关系名称	子串
关系符号
Latex
关系对象	字符串
关系元数	2
类型	偏序
全集	[math]\displaystyle{ \Sigma^*\times \Sigma^* }[/math]

对 [math]\displaystyle{ \Sigma }[/math] 上的字符串 [math]\displaystyle{ s }[/math] 和 [math]\displaystyle{ t }[/math] ，若 [math]\displaystyle{ (\exists p,q\in \Sigma^*)(s = ptq) }[/math] ，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的子字符串(substring)，简称子串。

有人将字符串 [math]\displaystyle{ s }[/math] 的全部子串构成的集合记作 [math]\displaystyle{ \operatorname{Sub}(s) }[/math] 。

真子串
关系名称	真子串
关系符号
Latex
关系对象	字符串
关系元数	2
类型	拟序
全集	[math]\displaystyle{ \Sigma^*\times \Sigma^* }[/math]

若子串定义中， [math]\displaystyle{ (\exists p,q\in \Sigma^*)(pq\neq \varepsilon \land s = ptq) }[/math] ，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的真子串(proper substring)。

子串
运算名称	子串
运算符号
Latex
运算对象	字符串, 自然数
运算元数	3
运算结果	字符串
定义域	[math]\displaystyle{ \Sigma^* \times \mathbb{N}\times \mathbb{N} }[/math]
陪域	[math]\displaystyle{ \Sigma }[/math]

对给定字符串 [math]\displaystyle{ a=\mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n }[/math] 和自然数 [math]\displaystyle{ i,j }[/math] ，其中 [math]\displaystyle{ 0\leq i \leq j\leq n }[/math] ，取 [math]\displaystyle{ \mathtt{a}_i \cdots \mathtt{a}_{j} }[/math] 的运算也称为字符串 [math]\displaystyle{ a }[/math] 从 [math]\displaystyle{ i }[/math] 到 [math]\displaystyle{ j }[/math] 的子串。有人记作 [math]\displaystyle{ s_{i\cdots j} }[/math] 或 [math]\displaystyle{ s_{(i+1)\cdots j} }[/math] 。特别地， [math]\displaystyle{ i=j }[/math] 时是空串。

性质

子串关系是一个偏序关系，意味着其是自反关系、传递关系、反对称关系。特别地，空串是任意字符串的子串，是任意非空字符串的真子串。

子串的子串仍然是子串，即 [math]\displaystyle{ (s_{i\cdots j})_{k \cdots l} = s_{i+k-1,i+l-1} }[/math] ，如果用自带 +1 的下标则是 [math]\displaystyle{ (s_{i\cdots j})_{k \cdots l} = s_{i+k,i+l} }[/math] 。

子串的长度不超过原字符串的长度，即若 [math]\displaystyle{ t }[/math] 是[math]\displaystyle{ s }[/math] 的子串，则有 [math]\displaystyle{ |t|\leq|s| }[/math] 。 若为真子串，有 [math]\displaystyle{ |t| \lt |s| }[/math] 。

字符串所有子串的个数满足 [math]\displaystyle{ |\operatorname{Sub}(s)| = \tfrac{1}{2}|s|(|s|+1) + 1 }[/math] ，也就是每个可能的长度 [math]\displaystyle{ i }[/math] 下各有 [math]\displaystyle{ |s|-i+1 }[/math] 个子串, 最后加上一个空串。

子串总是能拆分成一个前缀的后缀，也是一个后缀的前缀。如果将原字符串拆分称前后缀两部分， [math]\displaystyle{ s=uv }[/math] ，则 [math]\displaystyle{ t }[/math] 或者是 [math]\displaystyle{ u }[/math] 的子串，或者是 [math]\displaystyle{ v }[/math] 的子串，或者是 [math]\displaystyle{ u }[/math] 的后缀与 [math]\displaystyle{ v }[/math] 的后缀的连接。

反转运算保持子串和真子串关系。

字符串
特殊字符串	空字符串 [math]\displaystyle{ \varepsilon }[/math]
运算	长度 [math]\displaystyle{ |\bullet| }[/math]
	连接 [math]\displaystyle{ \bullet \bullet }[/math]
	自连接 [math]\displaystyle{ \bullet^n }[/math]	Kleene 闭包 [math]\displaystyle{ \bullet^* }[/math] 、 Kleene+ 闭包 [math]\displaystyle{ \bullet^+ }[/math]
	反转 [math]\displaystyle{ \bullet^\mathrm{R} }[/math]
关系	子串	子列
	前缀、后缀	公共前后缀