题意：将字符串s的每个后缀化成B数组，然后对B数组进行字典序排序。
题解：
网友提醒后补充一下：对于 " b b b " "bbb" "bbb"这个的A应该是 0110 0110 0110,D为空，具体的分割的原则有两个一是D不会因为分割受到影响（第一个a和第一个b会变成0嘛，才能直接根据整个串的B数组的后缀数组rank值来排D）且D必须大于1开头，这样子A的影响才能绝对大于D的影响，第二个是A一定要以0开头，以0结尾，中间为1，如果后缀中没有‘a’’或’b’就在末尾补一个，容易想到这样并不会影响排名的结果(简单理解一下，如果都是没有b或a的，如0111,011,01那么都会长度加一，而不需要长度加一的部分，如果长度与其相同，如0110与0111长度相同，但0111>0110而这跟0111变成01110后01110>0110是一样的），且能实现根据A的长度来对A排序
正文：、
对于特定的后缀字符串 t t t，其化成B数组的值时，第一个a的值为0，第一个b的值为0，在第一个a和第一个b之间的值为1。如 t = “ a a a a b a a a b ” t=“aaaabaaab” t=“aaaabaaab”,则 B ( t ) = 011102114 B(t)=011102114 B(t)=011102114,前半段为 01110 01110 01110。
这样，每个后缀子串就都有一个 T T T, B ( T ) = A D B(T)=AD B(T)=AD其中 A = 01..10 A=01..10 A=01..10
对于字典序排序，显然前半段的影响较大，那么将对A进行排序，再对A相同的D进行排序即可。
具体看一个例子；
给定字符串
a a b a a b a a a b a aabaabaaaba aabaabaaaba(
先化成B数组：
B ( t 1 ) = 01021321142 , A 1 = 010 , D 1 = 21321142 B(t_1)=01021321142, A_1=010, D_1=21321142 B(t1​)=01021321142,A1​=010,D1​=21321142
B ( t 2 ) = 0021321142 , A 2 = 00 , D 2 = 21321142 B(t_2)=0021321142, A_2=00, D_2=21321142 B(t2​)=0021321142,A2​=00,D2​=21321142
B ( t 3 ) = 001321142 , A 3 = 00 , D 3 = 1321142 B(t_3)=001321142, A_3=00,D_3=1321142 B(t3​)=001321142,A3​=00,D3​=1321142
B ( t 4 ) = 01021142 , A 4 = 010 , D 4 = 21142 B(t_4)=01021142,A_4=010,D_4=21142 B(t4​)=01021142,A4​=010,D4​=21142
B ( t 5 ) = 0021142 , A 5 = 00 , D 5 = 21142 B(t_5)=0021142,A_5=00,D_5=21142 B(t5​)=0021142,A5​=00,D5​=21142
B ( t 6 ) = 001142 , A 6 = 00 , D 6 = 1142 B(t_6)=001142,A_6=00,D_6=1142 B(t6​)=001142,A6​=00,D6​=1142
B ( t 7 ) = 01102 , A 7 = 0110 , D 7 = 2 B(t_7)=01102,A_7=0110,D_7=2 B(t7​)=01102,A7​=0110,D7​=2
B ( t 8 ) = 0102 , A 8 = 010 , D 8 = 2 B(t_8)=0102,A_8=010,D_8=2 B(t8​)=0102,A8​=010,D8​=2
B ( t 9 ) = 002 , A 9 = 00 , D 9 = 2 B(t_9)=002,A_9=00,D_9=2 B(t9​)=002,A9​=00,D9​=2
B ( t 1 0 ) = 00 , A 10 = 00 , D 1 0 = 空 B(t_10)=00,A_{10}=00,D_10=空 B(t1​0)=00,A10​=00,D1​0=空,给其rk排名规定为-1
B ( t 1 1 ) = 00 , A 11 = 00 , D 1 1 = 空 B(t_11)=00,A_{11}=00,D_11=空 B(t1​1)=00,A11​=00,D1​1=空给其rk排名规定为-2
易知若 A i < A j A_i<A_j Ai​<Aj​则 B ( t i ) < B ( t j ) B(t_i)<B(t_j) B(ti​)<B(tj​)
那么根据A来对 B B B进行第一步排序，然后对相同的A的B进行根据D内部排序即可
对 A A A排序直接看 A A A的长度即可，长度越长 A A A越大
而求A的长度，只需要求第一个 a a a与第一个 b b b的位置就可以知道了，这可以用滑动窗口O(n)时间内求得
观察 D D D序列，如果我们队整个字符串求 B ′ B' B′值，那么显然D值与 B ’ B’ B’相同长度的的后缀是一样的，则对 B ′ B' B′做一次求后缀数组得 r a n k rank rank值后，则 r a n k [ i + ∣ A i ∣ ] 即 是 D i rank[i+|A_i|]即是D_i rank[i+∣Ai​∣]即是Di​的排名了。
而这可以直接sort一下就行了。
代码：

#include <bits/stdc++.h>
using namespace std;
struct _IO{_IO(){ios::sync_with_stdio(0);cin.tie(0);}}_io;
typedef long long ll; typedef long double db;
const int N = 2e6 + 5, M = 1e9 + 7;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];
// px[i] = rk[id[i]]（用于排序的数组所以叫 px）

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void da(int *s, int n, int m) {
    int i,p,w;
    for(int i=0;i<=n;i++)cnt[i]=0;
 for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w <<= 1, m = p) {  // m=p 就是优化计数排序值域
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    //memset(cnt, 0, sizeof(cnt));
    for(int i=0;i<=n;i++)cnt[i]=0;
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    for(int i=0;i<=n;i++)oldrk[i]=rk[i];
    //memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }

}

int n;
struct node {
  int x, y;
  bool operator < (const node &b) const {
    if (y - x == b.y - b.x) {
      return rk[y+1] < rk[b.y+1];
    }
    return y - x < b.y - b.x;
  }
} a[N];
int b[N];
char s[N];
int main() {
  while (cin >> n) {
    cin >> s+1;
    int x = -1, y = -1;
    for (int i = 1; i <= n; i++) {
      b[i] = 0;
      if (s[i] == 'a') {
        if (x != -1) b[i] = i - x;
        x = i;
      } else {
        if (y != -1) b[i] = i - y;
        y = i;
      }
    }
    for(int i=1;i<=n;i++)
    {
        b[i]++;
    }
    da(b, n, n);//后缀数组求出rank数组
    for(int i=1;i<=n;i++)
    x = y = n+1;
    for (int i = n ; i >= 1; i--) {
      if (s[i] == 'a') {
        a[i] = {i, y};
        x = i;
      } else {
        a[i] = {i, x};
        y = i;
      }
    }
    rk[n+1] = -1;
    rk[n+2] = -2;
    sort(a+1, a + n+1);
    for (int i = 1; i <=n; i++) {
      cout << a[i].x  << ' ';
    }
    cout << '\n';
  }
}