Lyndon 分解

Lyndon 分解

首先我们介绍 Lyndon 分解的概念。

Lyndon 串：对于字符串 ，如果 的字典序严格小于 的所有后缀的字典序，我们称 是简单串，或者 Lyndon 串。举一些例子，a,b,ab,aab,abb,ababb,abcd 都是 Lyndon 串。当且仅当 的字典序严格小于它的所有非平凡的（非平凡：非空且不同于自身）循环同构串时， 才是 Lyndon 串。

Lyndon 分解：串 的 Lyndon 分解记为 ，其中所有 为简单串，并且他们的字典序按照非严格单减排序，即 。可以发现，这样的分解存在且唯一。

Duval 算法

Duval 可以在 的时间内求出一个串的 Lyndon 分解。

首先我们介绍另外一个概念：如果一个字符串 能够分解为 的形式，其中 是一个 Lyndon 串，而 是 的前缀（ 可能是空串），那么称 是近似简单串（pre-simple），或者近似 Lyndon 串。一个 Lyndon 串也是近似 Lyndon 串。

Duval 算法运用了贪心的思想。算法过程中我们把串 分成三个部分 ，其中 是一个 Lyndon 串，它的 Lyndon 分解已经记录； 是一个近似 Lyndon 串； 是未处理的部分。

整体描述一下，该算法每一次尝试将 的首字符添加到 的末尾。如果 不再是近似 Lyndon 串，那么我们就可以将 截出一部分前缀（即 Lyndon 分解）接在 末尾。

我们来更详细地解释一下算法的过程。定义一个指针 指向 的首字符，则 从 遍历到 （字符串长度）。在循环的过程中我们定义另一个指针 指向 的首字符，指针 指向 中我们当前考虑的字符（意义是 在 的上一个循环节中对应的字符）。我们的目标是将 添加到 的末尾，这就需要将 与 做比较：

1. 如果 ，则将 添加到 末尾不会影响它的近似简单性。于是我们只需要让指针 自增（移向下一位）即可。
2. 如果 ，那么 就变成了一个 Lyndon 串，于是我们将指针 自增，而让 指向 的首字符，这样 就变成了一个循环次数为 1 的新 Lyndon 串了。
3. 如果 ，则 就不是一个近似简单串了，那么我们就要把 分解出它的一个 Lyndon 子串，这个 Lyndon 子串的长度将是 ，即它的一个循环节。然后把 变成分解完以后剩下的部分，继续循环下去（注意，这个情况下我们没有改变指针 ），直到循环节被截完。对于剩余部分，我们只需要将进度“回退”到剩余部分的开头即可。

代码实现

下面的代码返回串 的 Lyndon 分解方案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// C++ Version
// duval_algorithm
vector<string> duval(string const& s) {
  int n = s.size(), i = 0;
  vector<string> factorization;
  while (i < n) {
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j])
        k = i;
      else
        k++;
      j++;
    }
    while (i <= k) {
      factorization.push_back(s.substr(i, j - k));
      i += j - k;
    }
  }
  return factorization;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# Python Version
# duval_algorithm
def duval(s):
    n, i = len(s), 0
    factorization = []
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            factorization.append(s[i : i + j - k])
            i += j - k
    return factorization

复杂度分析

接下来我们证明一下这个算法的复杂度。

外层的循环次数不超过 ，因为每一次 都会增加。第二个内层循环也是 的，因为它只记录 Lyndon 分解的方案。接下来我们分析一下内层循环。很容易发现，每一次在外层循环中找到的 Lyndon 串是比我们所比较过的剩余的串要长的，因此剩余的串的长度和要小于 ，于是我们最多在内层循环 次。事实上循环的总次数不超过 ，时间复杂度为 。

最小表示法（Finding the smallest cyclic shift）

对于长度为 的串 ，我们可以通过上述算法寻找该串的最小表示法。

我们构建串 的 Lyndon 分解，然后寻找这个分解中的一个 Lyndon 串 ，使得它的起点小于 且终点大于等于 。可以很容易地使用 Lyndon 分解的性质证明，子串 的首字符就是 的最小表示法的首字符，即我们沿着 的开头往后 个字符组成的串就是 的最小表示法。

于是我们在分解的过程中记录每一次的近似 Lyndon 串的开头即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// C++ Version
// smallest_cyclic_string
string min_cyclic_string(string s) {
  s += s;
  int n = s.size();
  int i = 0, ans = 0;
  while (i < n / 2) {
    ans = i;
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j])
        k = i;
      else
        k++;
      j++;
    }
    while (i <= k) i += j - k;
  }
  return s.substr(ans, n / 2);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# Python Version
# smallest_cyclic_string
def min_cyclic_string(s):
    s += s
    n = len(s)
    i, ans = 0, 0
    while i < n / 2:
        ans = i
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            i += j - k
    return s[ans : ans + n / 2]

习题

• UVA #719 - Glass Beads

  本页面主要译自博文 Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига 与其英文翻译版 Lyndon factorization。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

build本页面最近更新：2022/1/4 21:58:45，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：iamtwz, orzAtalod, sshwy, StudyingFather, Chrogeek, diauweb, Enter-tainer, hqztrue, ksyx, llh721113, Soresen, Suyun514, Xeonacid
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论