B-Suffix Array 题解

A. B-Suffix Array

给出一个字符串，定义一个字符串 ~ 对应的 ~ 满足 ，如果不存在这样的 ，那么 ，现在要求将 的所有后缀按照其对应的 序列的字典序排列。

题解很神，用到一个神仙结论直接切飞，原文为（为了好看些，我自己稍微加了点 LaTeX 元素）：

Let
The B-Suffix Array is equivalent to the suffix array of

有了这个结论，加一点代码实现细节，就可以 这题。

这里先讲做法，再讲证明。

对于不存在这样的 的 ，我们要让他比其他 都大，设为 ，然后最后再放一个 在 的末尾，最后求出 的后缀数组，去掉最后一位倒着输出就是答案。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000010

int n,s[maxn];char S[maxn];
int fir[maxn],sec[maxn],sa[maxn],c[maxn];
void get_SA()
{
    int m=n;
    for(int i=1;i<=n;i++)c[fir[i]=s[i]]++;
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i>=1;i--)sa[c[fir[i]]--]=i;
    for(int k=1,tot;k<n;k<<=1)
    {
        tot=0;
        for(int i=n-k+1;i<=n;i++)sec[++tot]=i;
        for(int i=1;i<=n;i++)if(sa[i]>k)sec[++tot]=sa[i]-k;

        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[fir[i]]++;
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[fir[sec[i]]]--]=sec[i];

        for(int i=1;i<=n;i++)swap(fir[i],sec[i]);
        fir[sa[1]]=tot=1;
        for(int i=2;i<=n;i++)
        if(sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+k]==sec[sa[i-1]+k])fir[sa[i]]=tot;
        else fir[sa[i]]=++tot;
        if(tot==n)break; m=tot;
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        scanf("%s",S+1);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++)if(S[j]==S[i]){s[i]=j-i;break;}
            if(!s[i])s[i]=n;
        }
        n++;s[n]=n;get_SA();
        for(int i=n-1;i>=1;i--)printf("%d ",sa[i]);printf("\n");
        for(int i=1;i<=n;i++)s[i]=fir[i]=sec[i]=sa[i]=c[i]=0;
    }
}

证明：

首先对 和 要有一点感性的认识， 相当于前面最近的一个与 相同的字符到 的距离，而 相当于后面的最近的与 相同的字符到 的距离。

对于第 个位置，假设位置 是后面的最近的相同字符，那么可以发现，，也就是说，将 左移一位 就能得到 ，这里的左移一位就是将 放到上一个与 字符相同的位置。

考虑一个特殊的情况。

对于一个后缀，考虑 数组开头的一段，肯定是这样的：

那两个 就是第一次出现的 和 字符，因为他们没有上一个相同的字符。

考虑两个 中间 序列的长度，他的长度越长，字典序就会越大，例如这两个 数组：

显然下面那个字典序要大，因为第四位它是 而上面那个是 。

然后考虑他们对应的 数组，是长这样的：

其中， 都大于 。

此时可以发现，上面那个的字典序反而要小了。

也就是说，对于开头的一段 长度不同的两个后缀，如果 的 比 的 字典序要小，那么 的 一定比 的 的字典序要大。

再考虑一般情况。

假设两个后缀 的 序列有一段前缀是相同的，那么 的这一段前缀肯定也是相同的，不妨设这段前缀以若干个 结尾，那么对于第一个不同的位，肯定满足一个后缀的这一位是 ，另一个后缀的这一位是 ，像这样：

第一个不同的位是这一段中的第三位，然后他们对应的 序列就是：

第三位的 比 小，所以后缀 的 的字典序比后缀 的 的字典序要小。

再考虑他们的 序列，也就是将 左移一位，由于他们 序列的前面部分都是相同的，所以上一个 出现的位置是相同的，左移一位后 和 就会同时移到那个位置，像这样：

然后你可以发现，在 之前的位都是相同的，也就是说， 之间的大小比较决定了这两个后缀的字典序。

观察一开始 的位置，可以发现 那个位置离上一个 要更远一些，即满足 ，所以此时 的 的字典序比 的 的字典序要大。

综合上述两种情况，可以知道，对于两个后缀 ，假如 的 的字典序比 的 的字典序要小，那么总有 的 的字典序比 的 的字典序要大。

所以，求出 的后缀数组再反过来就是答案。

证毕。

仔细思考，可以发现这个 相对于 的优越性就在于：一个后缀的 一定是 整个序列的 的 一段后缀，并且这两个后缀的位置是相对应的，所以将 求出后缀数组，就相当于将原字符串的后缀进行排序了。而 不一样，对于每个后缀，他的 不一定是 整个序列的 的 一段后缀，所以不能直接上后缀排序。

再讲一个细节，就是为什么末尾要放一个 。

假如末尾是 的话，就对应两个后缀： 和 ，他们的 数组分别为 和 ，所以 的 的字典序比 的小，那么 应该排在 前面。

而注意到我们最后是要将 的 数组反过来的，也就是说，反过来之前， 的 应该比 的要大。

但是事实上他们的 分别为 和 ， 的 是要比 的 小的，而在末尾加一个 就可以避免这个问题，具体可以结合样例的第三组数据理解。