CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== Lyndon 分解学习 =====

首先介绍 Lyndon 串。设有串 $w$，若对于所有 $w=uv,u,v\neq\varepsilon$，有 $w<vu$，称该串为 Lyndon 串。

==== 性质 1 ====

Lyndon 串不存在一个真子串，既是前缀又是后缀。

**证明**：设 $u$ 是这样的一个串，那么 $w=uv'$ 且 $w=v''u$。那么由定义我们有 $w<v'u$ 且 $w<uv''$。因此 $uv'<uv''$ 且 $v''u<v'u$。那么 $v'<v''$ 且 $v''<v'$，矛盾。

==== 性质 2 ====

串 $w$ 是 Lyndon 串，当且仅当所有真后缀 $v$ 满足 $w<v$。

**证明**：若对所有 $v$ 满足 $w<v$，设 $w=uv$，由于 $uv<v$，因此 $uv<vu$。

若串 $w$ 是 Lyndon 串，由于 $uv<vu$，且根据性质 1，$v$ 不是 $w$ 的前缀，因此 $uv<v$。

==== 性质 3 ====

设有 Lyndon 串 $u,v$，$uv$ 是 Lyndon 串当且仅当 $u<v$。

**证明**：若 $uv$ 是 Lyndon 串，根据性质 2，$u<uv<v$。

若 $u<v$，设 $s$ 是 $uv$ 的一个真后缀，那么 $s=u'v$，$s=v$ 或 $s=v'$。其中 $u',v'$ 是 $u,v$ 的真后缀。

对于第一种情况，$u<u'$，且 $u$ 不是 $u'$ 的前缀，因此 $uv<u'v$。

对于第二种情况，若 $u$ 不是 $v$ 的前缀，由于 $u<v$，因此 $uv<v$。

若 $u$ 是 $v$ 的前缀，那么有 $v=uv''$，其中 $v''$ 是 $v$ 的一个真后缀。因此 $v<v''$，$uv<uv''=v$。

总而言之，$uv<v$。

对于第三种情况，$uv<v<v'$。

==== 性质 4 ====

设有 Lyndon 串 $u,v$，$u<v$，对于任何 $k_{1},k_{2}\ge1$ 有 $u^{k_{1}}v^{k_{2}}$ 是 Lyndon 串。

**证明**：归纳法可证明 $u^{k_{1}}v$ 是 Lyndon 串。而由于 $v$ 是 $u^{k_{1}}v^{k'_{2}}$ 的后缀，因而 $u^{k_{1}}v^{k'_{2}+1}$ 仍是 Lyndon 串。

==== 性质 5 ====

设 $u\in A^{*}$，$v\in A^{+}$，$uv$ 是 Lyndon 串。若 $a\in A$，且 $v<a$，那么 $ua$ 是 Lyndon 串。

**题解**：$u=\varepsilon$ 时显然。

设 $s=u'a$ 是 $ua$ 的一个真后缀。已知 $uv<u'v<u'a$。因此 $u$ 显然不是 $u'a$ 的前缀。那么有 $ua<u'v<u'a$。

论文 19 页，太长了，有缘再见 :)
CVBB ACM Team

用户工具

站点工具

页面工具
