Visits: 766

一个很冷门的字符串算法

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;
}

参考资料

• OI Wiki Lyndon 分解
• wucstdio 题解 P6127 【【模板】Lyndon 分解】