A 思维

思路

函数 $B$ 关于字符串 $S$ 的后缀数组并不好求，因为每个 $S$ 的后缀并不是 $B(S)$ 的后缀，我们尝试正难则反。

因此，我们考虑函数 $F$，满足：

  1. $F(s_1s_2…s_n) = f_1f_2…f_n$
  2. $f_i = \min \limits_{i \lt j \And s_i == s_j}(j - i)$
  3. 如果找不到这样的 $j$，$f_i = \inf$

可以发现一个01字符串 $S$，它对应的 $B(S)$ 越大，那么它的 $F(S)$ 越小，可知 $B$ 与 $F$ 是反序关系。

由于每个 $S$ 的后缀就是 $F(S)$ 的后缀，因此 $F(S)$ 的后缀数组很好求，根据反序关系，倒过来就是 $B(S)$ 的后缀数组了。

时间复杂度：$O(n)$ 或 $O(n \log n)$

代码

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 5;

char buf[N];
int s[N];
int sa[N];

inline void count_sort(int* data, int* id, int n, int max_val) {
    static int cnt[N], p[N];
    memset(cnt, 0, 4 * (max_val + 1));
    for (int i = 1; i <= n; ++i) p[i] = data[id[i]];
    for (int i = 1; i <= n; ++i) ++cnt[p[i]];
    for (int i = 1; i <= max_val; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[p[i]]--] = id[i];
}

inline bool cmp(int* id, int n, int x, int y, int w) {
    int u = x + w > n ? 0 : id[x + w];
    int v = y + w > n ? 0 : id[y + w];
    return u == v && id[x] == id[y];
}

void suffix_sort(int n) {
    static int buf[2][N];
    int* rk = buf[0], * id = buf[1], max_val = 0;
    for (int i = 1; i <= n; ++i) {
        rk[i] = s[i], id[i] = i;
        max_val = max(rk[i], max_val);
    }
    count_sort(rk, id, n, max_val);
    for (int w = 1; w < n; w *= 2) {
        int tot = 0;
        for (int i = n - w + 1; i <= n; ++i) id[++tot] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > w) id[++tot] = sa[i] - w;
        count_sort(rk, id, n, max_val);
        swap(rk, id);
        rk[sa[1]] = tot = 1;
        for (int i = 2; i <= n; ++i) {
            rk[sa[i]] = cmp(id, n, sa[i], sa[i - 1], w) ? tot : ++tot;
        }
        if (tot >= n) break;
        max_val = tot;
    }
}

int nxt[N];

int main() {
    int n;
    while(~scanf("%d", &n)) {
        scanf("%s", buf + 1);
        int last[2] = {0, 0};
        for (int i = n; i >= 1; --i) {
            nxt[i] = last[buf[i] - 'a'];
            last[buf[i] - 'a'] = i;
        }
        for (int i = 1; i <= n; ++i) {
            if (nxt[i] == 0) s[i] = n;
            else s[i] = nxt[i] - i;
        }
        s[n + 1] = n + 1;
        suffix_sort(n + 1);
        for (int i = n; i >= 1; --i) {
            printf("%d%c", sa[i], "\n "[i != 1]);
        }
    }
    return 0;
}