跳转至

Lyndon 分解

定義

首先我們介紹 Lyndon 分解的概念。

Lyndon 串：對於字符串 \(s\)，如果 \(s\) 的字典序嚴格小於 \(s\) 的所有後綴的字典序，我們稱 \(s\) 是簡單串，或者 Lyndon 串。舉一些例子，a,b,ab,aab,abb,ababb,abcd 都是 Lyndon 串。當且僅當 \(s\) 的字典序嚴格小於它的所有非平凡的（非平凡：非空且不同於自身）循環同構串時，\(s\) 才是 Lyndon 串。

Lyndon 分解：串 \(s\) 的 Lyndon 分解記為 \(s=w_1w_2\cdots w_k\)，其中所有 \(w_i\) 為簡單串，並且他們的字典序按照非嚴格單減排序，即 \(w_1\ge w_2\ge\cdots\ge w_k\)。可以發現，這樣的分解存在且唯一。

Duval 算法

解釋

Duval 可以在 \(O(n)\) 的時間內求出一個串的 Lyndon 分解。

首先我們介紹另外一個概念：如果一個字符串 \(t\) 能夠分解為 \(t=ww\cdots\overline{w}\) 的形式，其中 \(w\) 是一個 Lyndon 串，而 \(\overline{w}\) 是 \(w\) 的前綴（\(\overline{w}\) 可能是空串），那麼稱 \(t\) 是近似簡單串（pre-simple），或者近似 Lyndon 串。一個 Lyndon 串也是近似 Lyndon 串。

Duval 算法運用了貪心的思想。算法過程中我們把串 \(s\) 分成三個部分 \(s=s_1s_2s_3\)，其中 \(s_1\) 是一個 Lyndon 串，它的 Lyndon 分解已經記錄；\(s_2\) 是一個近似 Lyndon 串；\(s_3\) 是未處理的部分。

過程

整體描述一下，該算法每一次嘗試將 \(s_3\) 的首字符添加到 \(s_2\) 的末尾。如果 \(s_2\) 不再是近似 Lyndon 串，那麼我們就可以將 \(s_2\) 截出一部分前綴（即 Lyndon 分解）接在 \(s_1\) 末尾。

我們來更詳細地解釋一下算法的過程。定義一個指針 \(i\) 指向 \(s_2\) 的首字符，則 \(i\) 從 \(1\) 遍歷到 \(n\)（字符串長度）。在循環的過程中我們定義另一個指針 \(j\) 指向 \(s_3\) 的首字符，指針 \(k\) 指向 \(s_2\) 中我們當前考慮的字符（意義是 \(j\) 在 \(s_2\) 的上一個循環節中對應的字符）。我們的目標是將 \(s[j]\) 添加到 \(s_2\) 的末尾，這就需要將 \(s[j]\) 與 \(s[k]\) 做比較：

  1. 如果 \(s[j]=s[k]\)，則將 \(s[j]\) 添加到 \(s_2\) 末尾不會影響它的近似簡單性。於是我們只需要讓指針 \(j,k\) 自增（移向下一位）即可。
  2. 如果 \(s[j]>s[k]\)，那麼 \(s_2s[j]\) 就變成了一個 Lyndon 串，於是我們將指針 \(j\) 自增，而讓 \(k\) 指向 \(s_2\) 的首字符，這樣 \(s_2\) 就變成了一個循環次數為 1 的新 Lyndon 串了。
  3. 如果 \(s[j]<s[k]\)，則 \(s_2s[j]\) 就不是一個近似簡單串了，那麼我們就要把 \(s_2\) 分解出它的一個 Lyndon 子串，這個 Lyndon 子串的長度將是 \(j-k\)，即它的一個循環節。然後把 \(s_2\) 變成分解完以後剩下的部分，繼續循環下去（注意，這個情況下我們沒有改變指針 \(j,k\)），直到循環節被截完。對於剩餘部分，我們只需要將進度「回退」到剩餘部分的開頭即可。

實現

下面的代碼返回串 \(s\) 的 Lyndon 分解方案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 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
# 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

複雜度分析

接下來我們證明一下這個算法的複雜度。

外層的循環次數不超過 \(n\)，因為每一次 \(i\) 都會增加。第二個內層循環也是 \(O(n)\) 的，因為它只記錄 Lyndon 分解的方案。接下來我們分析一下內層循環。很容易發現，每一次在外層循環中找到的 Lyndon 串是比我們所比較過的剩餘的串要長的，因此剩餘的串的長度和要小於 \(n\)，於是我們最多在內層循環 \(O(n)\) 次。事實上循環的總次數不超過 \(4n-3\)，時間複雜度為 \(O(n)\)。

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

對於長度為 \(n\) 的串 \(s\)，我們可以通過上述算法尋找該串的最小表示法。

我們構建串 \(ss\) 的 Lyndon 分解，然後尋找這個分解中的一個 Lyndon 串 \(t\)，使得它的起點小於 \(n\) 且終點大於等於 \(n\)。可以很容易地使用 Lyndon 分解的性質證明，子串 \(t\) 的首字符就是 \(s\) 的最小表示法的首字符，即我們沿着 \(t\) 的開頭往後 \(n\) 個字符組成的串就是 \(s\) 的最小表示法。

於是我們在分解的過程中記錄每一次的近似 Lyndon 串的開頭即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 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
# 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]

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：sshwy, StudyingFather, orzAtalod
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用