子列（字符串）
| 子序列 | |
|---|---|
| 术语名称 | 子序列 |
| 英语名称 | subsequence |
| 别名 | 子列 |
| 真子序列 | |
|---|---|
| 术语名称 | 真子序列 |
| 英语名称 | proper subsequence |
| 别名 | 真子列 |
子序列(subsequence)指两个字符串中一个字符串是另一个字符串作为序列的子序列，或者说，一个字符串是另一个字符串中不要求连续的字符按顺序组成的部分，一个字符串中插入一些其他字符可以得到另一个字符串。
定义
| 子序列 | |
|---|---|
| 关系名称 | 子序列 |
| 关系符号 | |
| Latex | |
| 关系对象 | 字符串 |
| 关系元数 | 2 |
| 类型 | 偏序 |
| 全集 | [math]\displaystyle{ \Sigma^*\times \Sigma^* }[/math] |
对 [math]\displaystyle{ \Sigma }[/math] 上的字符串 [math]\displaystyle{ s = \mathtt{s}_1 \mathtt{s}_2 \cdots \mathtt{s}_n }[/math] 和 [math]\displaystyle{ t = \mathtt{t}_1 \mathtt{t}_2 \cdots \mathtt{t}_m }[/math] ，若 [math]\displaystyle{ (\exists i_1,i_2\cdots,i_m\in \mathbb{N}^*)(i_1\lt i_2\lt \cdots\lt i_m \land \mathtt{s}_{i_1}=\mathtt{t}_1 \land \mathtt{s}_{i_2}=\mathtt{t}_2 \land \cdots \land \mathtt{s}_{i_m}=\mathtt{t}_m) }[/math] ，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的子序列(subsequence)，简称子列。
| 真子序列 | |
|---|---|
| 关系名称 | 真子序列 |
| 关系符号 | |
| Latex | |
| 关系对象 | 字符串 |
| 关系元数 | 2 |
| 类型 | 拟序 |
| 全集 | [math]\displaystyle{ \Sigma^*\times \Sigma^* }[/math] |
若子序列定义中， [math]\displaystyle{ s\neq t }[/math] 或者说 [math]\displaystyle{ n\gt m }[/math]，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的真子序列(proper subsequence)。