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; } }
证明:
首先对 和
要有一点感性的认识,
相当于前面最近的一个与
相同的字符到
的距离,而
相当于后面的最近的与
相同的字符到
的距离。
对于第 个位置,假设位置
是后面的最近的相同字符,那么可以发现,
,也就是说,将
左移一位
就能得到 ,这里的
左移一位
就是将 放到上一个与
字符相同的位置。
考虑一个特殊的情况。
对于一个后缀,考虑 数组开头的一段,肯定是这样的:
那两个 就是第一次出现的
和
字符,因为他们没有上一个相同的字符。
考虑两个 中间
序列的长度,他的长度越长,字典序就会越大,例如这两个
数组:
显然下面那个字典序要大,因为第四位它是 而上面那个是
。
然后考虑他们对应的 数组,是长这样的:
其中, 都大于
。
此时可以发现,上面那个的字典序反而要小了。
也就是说,对于开头的一段 长度不同的两个后缀,如果
的
比
的
字典序要小,那么
的
一定比
的
的字典序要大。
再考虑一般情况。
假设两个后缀 的
序列有一段前缀是相同的,那么
的这一段前缀肯定也是相同的,不妨设这段前缀以若干个
结尾,那么对于第一个不同的位,肯定满足一个后缀的这一位是
,另一个后缀的这一位是
,像这样:
第一个不同的位是这一段中的第三位,然后他们对应的 序列就是:
第三位的 比
小,所以后缀
的
的字典序比后缀
的
的字典序要小。
再考虑他们的 序列,也就是将
左移一位
,由于他们 序列的前面部分都是相同的,所以上一个
出现的位置是相同的,
左移一位
后 和
就会同时移到那个位置,像这样:
然后你可以发现,在 之前的位都是相同的,也就是说,
之间的大小比较决定了这两个后缀的字典序。
观察一开始 的位置,可以发现
那个位置离上一个
要更远一些,即满足
,所以此时
的
的字典序比
的
的字典序要大。
综合上述两种情况,可以知道,对于两个后缀 ,假如
的
的字典序比
的
的字典序要小,那么总有
的
的字典序比
的
的字典序要大。
所以,求出 的后缀数组再反过来就是答案。
证毕。
仔细思考,可以发现这个 相对于
的优越性就在于:一个后缀的
一定是 整个序列的
的 一段后缀,并且这两个后缀的位置是相对应的,所以将
求出后缀数组,就相当于将原字符串的后缀进行排序了。而
不一样,对于每个后缀,他的
不一定是 整个序列的
的 一段后缀,所以不能直接上后缀排序。
再讲一个细节,就是为什么末尾要放一个 。
假如末尾是 的话,就对应两个后缀:
和
,他们的
数组分别为
和
,所以
的
的字典序比
的小,那么
应该排在
前面。
而注意到我们最后是要将 的
数组反过来的,也就是说,反过来之前,
的
应该比
的要大。
但是事实上他们的 分别为
和
,
的
是要比
的
小的,而在末尾加一个
就可以避免这个问题,具体可以结合样例的第三组数据理解。