B-Suffix Array

题意：

一个字符串只含有a和b，先给出b数组的构造方式：
对于每个位置i来说：

  1. 如果存在一个位置j，使得j<i,且s[j] == s[i],则b[i]=i-j
  2. 否则b[i]=0
    现在对字符串每个后缀都构造B数组，并按照字典序排序

题解：

参考博客
题目标题就已经透露了一切，Suffix Array，说明这个题要用后缀数组来做，但是具体怎么做呢？
我们会发现，化为B数组的值后，第一个a的值肯定为0，第一个b的值肯定也为0，那么从第一个a到第一个b之间肯定都是1
比如“aaaabaaab”,则B(t) = 011102114，前半段为01110（也就是第一个a到第一个b），我们可以将B数组分为两部分，前半部为01110，后半部分为2114，这样字典序排序时，我们先对前半部分排序即可，如果前半部分一样再对后半部分排序
对于前半部分排序，直接比较长度即可，因为都是0开头，0结尾，中间是1，越长说明中间的1越多，且前半部分极好确定，直接找第一个a与b就行
那现在后半部分怎么确定呢？
Ai表示前半部分，DI表示后半部分
后半部分是数组B的后缀，我们直接后缀数组，得到rank值，rank[i+|Ai|]就是Di的排名
Rank[i]=后缀suf(i)的排名，也就是从第i位到最后一位构成的子串排名
这个题，秒极了
在这里插入图片描述

代码：

#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') {//从第i位开始的后缀，分为前部分Ai，范围[x,y]和后部分Bi 
        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';
  }
}