反转
| 反转 | |
|---|---|
| 术语名称 | 反转 |
| 英语名称 | reversal |
反转(reversal)指把一个字符串字符顺序反转构成一个字符串的运算。
定义
| 反转 | |
|---|---|
| 运算名称 | 反转 |
| 运算符号 | [math]\displaystyle{ ^\mathrm{R} }[/math] |
| Latex | ^\mathrm{R}
|
| 运算对象 | 字符串 |
| 运算元数 | 2 |
| 运算结果 | 字符串 |
| 定义域 | [math]\displaystyle{ \Sigma^* }[/math] |
| 陪域 | [math]\displaystyle{ \Sigma^* }[/math] |
对字符串 [math]\displaystyle{ a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n }[/math] ，称字符串 [math]\displaystyle{ \mathtt{a}_n \mathtt{a}_{n-1} \cdots \mathtt{a}_1 }[/math] 为字符串的反转(reversal)，记作 [math]\displaystyle{ a^\mathrm{R} }[/math] 。
性质
- 反转不改变字符串长度，即 [math]\displaystyle{ |a^\mathrm{R}|=|a| }[/math] 。
- 空串、长度为 1 的字符串反转保持不变： [math]\displaystyle{ \varepsilon^\mathrm{R} = \varepsilon }[/math] 。有这种性质的字符串称为回文串。
- 对合性： [math]\displaystyle{ (a^\mathrm{R})^\mathrm{R} = a }[/math] 。
- 与其他字符串运算联系：
- 在连接运算构成的幺半群上是一个反自同态： [math]\displaystyle{ (ab)^\mathrm{R} = b^\mathrm{R} a^\mathrm{R} }[/math] 。
- 与幂运算兼容 [math]\displaystyle{ (a^k)^\mathrm{R}=(a^\mathrm{R})^k }[/math]
- 交换前缀、后缀关系