公共前后缀
| 公共前后缀 | |
|---|---|
| 术语名称 | 公共前后缀 |
| 英语名称 | border |
| 公共真前后缀 | |
|---|---|
| 术语名称 | 公共真前后缀 |
| 英语名称 | proper border |
本条目没有一致可信的中文译名。
定义
| 公共前后缀 | |
|---|---|
| 关系名称 | 公共前后缀 |
| 关系符号 | |
| Latex | |
| 关系对象 | 字符串 |
| 关系元数 | 2 |
| 类型 | 偏序 |
| 全集 | [math]\displaystyle{ \Sigma^*\times \Sigma^* }[/math] |
对 [math]\displaystyle{ \Sigma }[/math] 上的字符串 [math]\displaystyle{ s }[/math] 和 [math]\displaystyle{ t }[/math] ，若 [math]\displaystyle{ t }[/math] 既是 [math]\displaystyle{ s }[/math] 的前缀，又是 [math]\displaystyle{ s }[/math] 的后缀，即 [math]\displaystyle{ (\exists q\in \Sigma^*)(s = tq)\land(\exists p\in \Sigma^*)(s = pt) }[/math] ，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的公共前后缀(border)。
| 公共真前后缀 | |
|---|---|
| 关系名称 | 公共真前后缀 |
| 关系符号 | |
| Latex | |
| 关系对象 | 字符串 |
| 关系元数 | 2 |
| 类型 | 偏序 |
| 全集 | [math]\displaystyle{ \Sigma^*\times \Sigma^* }[/math] |
上述定义中，若 [math]\displaystyle{ t }[/math] 既是 [math]\displaystyle{ s }[/math] 的真前缀，又是 [math]\displaystyle{ s }[/math] 的真后缀，则称字符串 [math]\displaystyle{ t }[/math] 是字符串 [math]\displaystyle{ s }[/math] 的公共真前后缀(proper border)。
注意：与其他常见用法不同，“公共真前后缀”中的“公共”一词不表示多个对象的公共（common）。这是因为“前后缀”一词经常作为前缀和后缀的合称，人们说 [math]\displaystyle{ s }[/math] 的前后缀时一般是指任意一个前缀或后缀，所以必须加上额外的修饰来表示同时成立。
性质
公共真前后缀关系是一个偏序关系，意味着其是自反关系、传递关系、反对称关系。特别地，空串是任意字符串的子串，是任意非空字符串的真子串。