前缀、后缀

前缀
术语名称	前缀
英语名称	prefix

后缀
术语名称	后缀
英语名称	suffix

前缀(prefix)指一个字符串是另一个字符串从头开始的子串。 后缀(suffix)指到结尾为止的子串。

定义

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

对 [math]\displaystyle{ \Sigma }[/math] 上的字符串 [math]\displaystyle{ s }[/math] 和 [math]\displaystyle{ t }[/math] ，若 [math]\displaystyle{ (\exists q\in \Sigma^*)(s = tq) }[/math] ，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的前缀(prefix)。

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

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

对 [math]\displaystyle{ \Sigma }[/math] 上的字符串 [math]\displaystyle{ s }[/math] 和 [math]\displaystyle{ t }[/math] ，若 [math]\displaystyle{ (\exists p\in \Sigma^*)(s = tp) }[/math] ，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的后缀(suffix)。

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

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

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

若以上定义中满足 [math]\displaystyle{ q\neq\varepsilon }[/math] 或 [math]\displaystyle{ p\neq\varepsilon }[/math] 则分别称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的真前缀(proper prefix)或真后缀(proper suffix)。

子串
运算名称	子串
运算符号
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{ t }[/math] 是[math]\displaystyle{ s }[/math] 的子串，则有 [math]\displaystyle{ |t|\leq|s| }[/math] 。 若为真前缀或真后缀，有 [math]\displaystyle{ |t| \lt |s| }[/math] 。

字符串所有前缀和所有后缀的个数满足 [math]\displaystyle{ |\operatorname{Pref}(s)| = |\operatorname{Suf}(s)| = |s|+1 }[/math] ，且其中元素长度与 [math]\displaystyle{ 0,1,\cdots,|s| }[/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]
关系	子串	子列
	前缀、后缀	公共前后缀