Lyndon 分解 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-02-22 18:29

点击数:242

一个很冷门的字符串算法

Lyndon 串

对于一个字符串,若其本身就是其最小后缀,则称它为 Lyndon 串。

形式化地,对于长度为 $n$ 的字符串 $s$,若满足对于 $i \in [2,n]$,都有 $s < s[i:n]$,则称其为 Lyndon 串。

Lyndon 分解

任意一个字符串都可以被唯一的分解成若干个字典序非严格递减的 Lyndon 串。

形式化地,对于长度为 $n$ 的字符串 $s$,存在唯一的若干个 Lyndon 串 $t_{1\dots m}$,满足 $s=t_1 + t_2 + \cdots + t_m$ 且 $t_1 \ge t_2 \ge \cdots \ge t_m$。

Duval 算法

Duval 算法可以在 $\mathcal O(n)$ 的时间求出一个字符串的 Lyndon 分解。

维护三个指针 $i,j,k$,这三个指针将整个字符串分成了四个部分 $s[1:i-1], s[i,k-1], s[j,k-1], s[k,n]$:

  • $s[1,i-1]$:这部分的 Lyndon 分解已经完成。
  • $s[i,k-1]$:这部分可以被表示成 $t^c + v$,其中 $t$ 是一个 Lyndon 串,$t^c$ 表示 $t$ 循环 $c$ 次,$v$ 是 $t$ 的一个可空真前缀。
  • $s[j,k-1]$:注意这部分是包含在上一个部分中的,其中 $j = k – |t|$。
  • $s[k,n]$:这部分还未处理,此时正在考虑 $k$。

考虑 $k$ 有三种情况:

  • $s_j = s_k$:可以将 $t$ 继续循环下去,因此 $j$ 往后移一位,考虑下一个 $k$。
  • $s_j < s_k$:可以将 $t^c + v + s_k$ 合并为一个 Lyndon 串,因此 $j$ 设为 $i$,考虑下一个 $k$。
  • $s_j > s_k$:可以将 $t$ 单独作为 Lyndon 分解中的一个串,然后从 $v$ 的开头开始重新考虑,因此 $i$ 设为 $v$ 的开头,$j,k$ 对应设为 $i,i+1$。

【模板】P6114 【模板】Lyndon 分解

const int N = 5e6 + 7;
int n, ans;
char s[N];

int main() {
    rds(s, n);
    int i = 1;
    while (i <= n) {
        int j = i, k = i + 1;
        while (k <= n && s[j] <= s[k]) j = s[j] == s[k++] ? j + 1 : i;
        while (i <= j) i += k - j, ans ^= i - 1;
    }
    print(ans);
    return 0;
}

最小表示法

一个字符串的最小表示定义为其所有循环同构中字典序最小的串。

形式化地,对于长度为 $n$ 的字符串 $s$,若 $p \in [1,n]$ 满足对于 $i \in [1, n]$,都有 $s[p:n] + s[1:p-1] \le s[i:n] + s[1:i-1]$,则称 $s[p:n] + s[1:p-1]$ 为 $s$ 的最小表示。

最小表示法可以使用 Lyndon 分解求出。

对于长度为 $n$ 的字符串 $s$,设 $t = s + s$,对 $t$ 进行 Lyndon 分解,找到首字符位置 $\le n$ 且最大的 Lyndon 串,这个串的首字符即最小表示法的首字符。

【模板】P1368 工艺 /【模板】最小表示法

const int N = 6e5 + 7;
int n, ans = 1, s[N];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(s[i]), s[i+n] = s[i];
    int i = 1;
    while (i <= n) {
        int j = i, k = i + 1;
        while (k <= n * 2 && s[j] <= s[k]) j = s[j] == s[k++] ? j + 1 : i;
        while (i <= j) i += k - j, ans = i <= n ? i : ans;
    }
    for (int i = 1; i <= n; i++) print(s[ans-1+i], " \n"[i==n]);
    return 0;
}

【例题】UVA719 Glass Beads

与上一题不同的是,这题要求位置最靠前。

只有一种情况下两道题的答案不一样,那就是字符串恰好为一个循环串的时候。

那么我们换一个写法即可,同时,推荐使用这种写法

const int N = 2e4 + 7;
int n, ans;
char s[N];

inline void solve() {
    rds(s, n);
    for (int i = 1; i <= n; i++) s[i+n] = s[i];
    int i = 1;
    while (i <= n) {
        ans = i;
        int j = i, k = i + 1;
        while (k <= n * 2 && s[j] <= s[k]) j = s[j] == s[k++] ? j + 1 : i;
        while (i <= j) i += k - j;
    }
    print(ans);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注