[关闭]
@qq290637843 2021-01-16T13:36:07.000000Z 字数 2715 阅读 421

林登串及林登分解

先给出几个之后会用到的引理，自己证明：

引理1：字符串的比较符号是一个全序。

引理2：如果两个字符串，则对任何字符串，之间的大小关系同之间的大小关系。

引理3：对任何字符串，之间的大小关系同之间的大小关系。

引理4：如果字符串不是的前缀，且，那么对任何，。

旋转：设，那么称为的一个旋转，如果和均非空，则称为的一个非平凡旋转（注意，非平凡只是要求两项非空，并没要求旋转完之后要和一开始不同，如"abcabc"也是"abcabc"的非平凡旋转）。

林登串：设为一非空字符串，如果小于其所有非平凡旋转，则称为林登串，记为。

定理1：一个字符串是林登串当且仅当其小于其所有非空严格后缀。
证明：
充分性：设且和非空。由于，故。
必要性：设且且和非空。考虑两种情况：
如果，由于是林登串，故，于是（引理2），于是（引理3），这和矛盾。
于是可知不是的前缀。如果那么（引理4），这和矛盾。
故。

定理2 如果且，那么。
证明：
首先说明。如果是的前缀，那么。于是由于，所以（引理3）。如果不是的前缀，那么直接使得。
现在考虑的非空严格后缀。如果是的严格后缀，那么。如果，那么。如果，那么由于，于是（引理4）。

定理3（林登定理） 任何字符串可以被唯一（也是唯一的）地表示为以下形式：且且。
证明：
存在性：首先，考虑将拆成单个字母的序列，接着，只要发现当前序列中任何两个相邻的林登串左小于右，则借助定理2将两个串连成一个串，直到序列中不存在相邻且左小于右的情况。
唯一性：假设存在两个分解方式，现在考虑设第一个不同的位置是和，不妨认为，于是（可能是），其中是的非空前缀（不一定严格）。于是，矛盾。

定理3所说的分解方式被称为林登分解。

接下来说明一个线性的实现林登分解的算法，Duval算法。

引理5 如果字符串，则对任何，。
证明：
设是的严格后缀。
如果是的前缀，于是根据可知，于是。
如果不是的前缀，于是由可知，于是。

根据引理5和定理2可知如下信息：
如果。那么当时：；当时：对任何，的林登分解正好就是个再连上的林登分解。

于是就有了下方的算法（下标从开始）：

  1. for (int i = 1, j, k; i <= n; ) {
  2.     for (k = i, j = k + 1; j <= n && s[j] >= s[k]; ++j) {
  3.         if (s[j] > s[k]) {
  4.             k = i;
  5.         } else {
  6.             ++k;
  7.         }
  8.     }
  9.     while (i <= k) {
  10.         lyndon[++cnt] = i + j - k - 1;
  11.         i += j - k;
  12.     }
  13. }

现在解释一下代码中分别在干什么：每当开始第二行的时候，已经完成了林登分解，且不可能再有变化，也就是说，实际还要解决的分解工作。注意每次到达第三行的时候，只有两种可能性：和，如果这时，就是说（对应于上文中的情况）。如果，则且正是重复的结果（对应于上文中的）。显然，如果新来的大于了，就进入的情况，也就是直接认定；如果新来的等于，则继续维持重复的延长；如果新来的小于了，则直接取出那些重复的林登串（九到十二行），并把问题变为分解。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注