UOJ #35. 后缀排序[后缀数组详细整理]

#35. 后缀排序

统计

这是一道模板题。

读入一个长度为 $n$ 的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $1$ 到 $n$ 。

除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出 $n - 1$ 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

输入格式

一行一个长度为 $n$ 的仅包含小写英文字母的字符串。

输出格式

第一行

第二行

样例一

input

ababa

output

5 3 1 4 2
1 3 0 2

explanation

排序后结果为：

a
aba
ababa
ba
baba

限制与约定

$1 \leq n \leq 10^{5}$

时间限制： $1 s$

空间限制： $256 MB$

下载

样例数据下载

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+7;
int len,maxx,sa[N],tsa[N],rank[N],trank[N],h[N],c[N];
char s[N];
void DA(){
    int p;
    memset(c,0,sizeof c);maxx=256;
    for(int i=1;i<=len;i++) c[rank[i]=s[i]]++;
    for(int i=2;i<=maxx;i++) c[i]+=c[i-1];
    for(int i=len;i;i--) sa[c[rank[i]]--]=i;
    trank[sa[1]]=p=1;
    for(int i=2;i<=len;i++){
        if(rank[sa[i]]!=rank[sa[i-1]]) p++;
        trank[sa[i]]=p;
    }
    for(int i=1;i<=len;i++) rank[i]=trank[i];
    for(int k=1;p<len;k<<=1,maxx=p){
        p=0;
        for(int i=len-k+1;i<=len;i++) tsa[++p]=i;
        for(int i=1;i<=len;i++) if(sa[i]>k) tsa[++p]=sa[i]-k;
        memset(c,0,sizeof c);
        for(int i=1;i<=len;i++) trank[i]=rank[tsa[i]];
        for(int i=1;i<=len;i++) c[trank[i]]++;
        for(int i=2;i<=maxx;i++) c[i]+=c[i-1];
        for(int i=len;i;i--) sa[c[trank[i]]--]=tsa[i];
        trank[sa[1]]=p=1;
        for(int i=2;i<=len;i++){
            if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++;
            trank[sa[i]]=p;
        }
        for(int i=1;i<=len;i++) rank[i]=trank[i];
    }
    for(int i=1,k=0;i<=len;i++){
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        h[rank[i]]=k;if(k>0) k--;
    }
}
int main(){
    scanf("%s",s+1);len=strlen(s+1);
    DA();
    for(int i=1;i<=len;i++) printf("%d ",sa[i]);putchar('
');
    for(int i=2;i<=len;i++) printf("%d ",h[i]);putchar('
');
    return 0;
}

代码理解版

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+5;
char s[N];
int len,maxx,sa[N],rank[N],sum[N],tsa[N],trank[N],height[N]; 
void Radix_sort(){
    maxx=256;
    memset(sum,0,sizeof sum);//起hash数组的作用，每次用都要清零
    for(int i=1;i<=len;i++){
        rank[i]=s[i];//用ASCⅡ码表覆初值，因为ASCⅡ码表是有序的（其他离散化也可以） 
        sum[rank[i]]++;//hash转化，rank为i的后缀数++
    }
    for(int i=2;i<=maxx;i++) sum[i]+=sum[i-1];//统计总数
    for(int i=len;i;i--) sa[sum[rank[i]]--]=i;//通过总数sum[]的性质，给sa[]数组覆初值
}
void DA(){
    int p;
    Radix_sort();//基数排序 
    //sa[i]表示rank是i的后缀的第一个字母在字符串中的位置
    trank[sa[1]]=1,p=1;
    for(int i=2;i<=len;i++){
        //初始化中sa[1]的trank[]还是在第一位，由此计算剩下的sa[i]的trank[i]值
        if(rank[sa[i]]!=rank[sa[i-1]]) p++;
        trank[sa[i]]=p;//如果i项不和i-1项相同，则属于下一个排名，否则并列p名
    }
    for(int i=1;i<=len;i++) rank[i]=trank[i];//将初始化得到的rank排名复制到rank[]数组中
    //--------------------------------------------------------初始化 
    //以下开始处理其他数据，利用倍增的思想，j每次乘以2，它表示合并的单体的长度
    for(int j=1;p<len;j<<=1,maxx=p){
        //当p==len时，即没有任何两个位置的排名并列，每一个位置都有自己的排名，循环结束
        p=0;//倍增后的排名又从0开始
        for(int i=len-j+1;i<=len;i++) tsa[++p]=i;
        //从len-j+1开始，他们的第二关键字没有，故为0。所以他们在新的trank（表示第二关键字的排名）中直接就从前面排起走，即tsa[++p]直接就是i这一个位置
        for(int i=1;i<=len;i++) if(sa[i]>j) tsa[++p]=sa[i]-j;
        //sa[i]中i从1->len，所以是有序的，按照排名从小到大的；
        //sa[i]>j表示sa[i]这个位置的字符成为过sa[i]-j的第二关键字，且sa[i]-j就是目前最小的了，
        //   那么关于第二关键字排序的数组tsa[]中的下一个元素就是sa[i]-j
        //tsa[i]表示在第二关键字排序中，排名为i的子串首字母在字符串中的位置
        memset(sum,0,sizeof sum);
        for(int i=1;i<=len;i++) trank[i]=rank[tsa[i]];
        //trank[i]表示第i个位置的后缀子串的在第二关键字排序中的排名
        for(int i=1;i<=len;i++) sum[trank[i]]++;
        for(int i=2;i<=maxx;i++) sum[i]+=sum[i-1];//同样对第二关键字进行hash统计
        for(int i=len;i;i--) sa[sum[trank[i]]--]=tsa[i];
        trank[sa[1]]=1,p=1;//求新的sa[ ]数组
        for(int i=2;i<=len;i++){
            if((rank[sa[i]]!=rank[sa[i-1]])||(rank[sa[i]+j]!=rank[sa[i-1]+j])) p++;
            //此处只需要在第一关键字和第二关键字中有一个不相同，就表明这两个的新
            //排名不能并列，即要p++。
            trank[sa[i]]=p;
        }
        for(int i=1;i<=len;i++) rank[i]=trank[i];//复制数组
    }
    for(int i=1,k=0;i<=len;i++){
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rank[i]]=k;if(k>0)k--;
    }
}
int main(){
    scanf("%s",s+1);len=strlen(s+1);
    DA();
    for(int i=1;i<=len;i++) printf("%d ",sa[i]);putchar('
');
    for(int i=2;i<=len;i++) printf("%d ",height[i]);putchar('
'); 
    return 0;
}

------------------------------------------------------

以下为常见的不解之处和问题

------------------------------------------------------

令h[i]=height[rank[i]],则h[i]>=h[i-1]-1

对于第i个后缀，设j=sa[rank[i] - 1]，也就是说j是i的按排名来的上一个字符串，按定义来i和j的最长公共前缀就是height[rank[i]]，我们现在就是想知道height[rank[i]]至少是多少，而我们要证明的就是至少是height[rank[i-1]]-1。

证明：

首先我们不妨设第i-1个字符串（这里以及后面指的“第?个字符串”不是按字典序排名来的，是按照首字符在字符串中的位置来的）按字典序排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。

这时，依据height[]的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rank[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。

第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为height[rank[i-1]]就是0了呀，那么无论height[rank[i]]是多少都会有height[rank[i]]>=height[rank[i-1]]-1，也就是h[i]>=h[i-1]-1。

第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面，要么就产生矛盾了。同时，第k个字符串和第i-1个字符串的最长公共前缀是height[rank[i-1]]，那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rank[i-1]]-1。

到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的字典序排名更靠前的那些字符串，谁和第i个字符串的相似度最高（这里说的相似度是指最长公共前缀的长度）？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rank[i]-1]。也就是说sa[rank[i]]和sa[rank[i]-1]的最长公共前缀至少是height[rank[i-1]]-1，那么就有height[rank[i]]>=height[rank[i-1]]-1，也即h[i]>=h[i-1]-1。
证明完毕。

4个比较基础的应用//摘抄自YxuanwKeith’blog

Q1：一个串中两个串的最大公共前缀是多少？
A1：这不就是Height吗？用rmq预处理，再O(1)查询。

Q2：一个串中可重叠的重复最长子串是多长？
A2：就是求任意两个后缀的最长公共前缀，而任意两个后缀的最长公共前缀都是Height 数组里某一段的最小值，那最长的就是Height中的最大值。

Q3：一个串种不可重叠的重复最长子串是多长？
A3：先二分答案，转化成判别式的问题比较好处理。假设当前需要判别长度为k是否符合要求，只需把排序后的后缀分成若干组，其中每组的后缀之间的Height 值都不小于k，再判断其中有没有不重复的后缀，具体就是看最大的SA值和最小的SA值相差超不超过k，有一组超过的话k就是合法答案。

Q4：一个字符串不相等的子串的个数是多少？
A4：每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不相同的前缀的个数。而且可以发现每一个后缀Suffix[SA[i]]的贡献是Len - SA[i] + 1,但是有子串算重复，重复的就是Heigh[i]个与前面相同的前缀，那么减去就可以了。最后，一个后缀Suffix[SA[i]]的贡献就是Len - SA[k] + 1 - Height[k]。
对于后缀数组更多的应用这里就不详细阐述，经过思考后每个人都会发现它的一些不同的用途，它的功能也许比你想象中的更强大！

三、后缀数组解题总结：

1、求单个子串的不重复子串个数。SPOJ 694、SPOJ 705.

这个问题是一个特殊求值问题。要认识到这样一个事实：一个字符串中的所有子串都必然是它的后缀的前缀。（这句话稍微有点绕...）对于每一个sa[i]后缀，它的起始位置sa[i]，那么它最多能得到该后缀长度个子串（n-sa[i]个），而其中有height[i]个是与前一个后缀相同的，所以它能产生的实际后缀个数便是n-sa[i]-height[i]。遍历一次所有的后缀，将它产生的后缀数加起来便是答案。

2、后缀的最长公共前缀。（记为lcp（x，y））

这是height数组的最基本性质之一。具体的可以参看罗穗骞的论文。后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这个描述可能有点乱，正规的说，令x=rank[i],y=rank[j]，x<y,那么lcp(i,j)=min(height[x+1],height[x+2]...height[y])。lcp(i,i)=n-sa[i]。解决这个问题，用RMQ的ST算法即可（我只会这个，或者用最近公共祖先那个转化的做法）。

3、最长重复子串（可重叠）

要看到，任何一个重复子串，都必然是某两个后缀的最长公共前缀。因为，两个后缀的公共前缀，它出现在这两个后缀中，并且起始位置时不同的，所以这个公共前缀必然重复出现两次以上（可重叠）。而任何两个后缀的最长公共前缀为某一段height值中的最小值，所以最大为height值中的最大值（即某个lcp(sa[i],sa[i+1]））。所以只要算出height数组，然后输出最大值就可以了。

4、最长重复不重叠子串 PKU1743

这个问题和3的唯一区别在于能否重叠。加上不能重叠这个限制后，直接求解比较困难，所以我们选择二分枚举答案，将问题转换为判定性问题。假设当时枚举的长度为k，那么要怎样判断是否存在长度为k的重复不重叠子串呢？

首先，根据height数组，将后缀分成若干组，使得每组后缀中，后缀之间的height值不小于k。这样分组之后，不难看出，如果某组后缀数量大于1，那么它们之中存在一个公共前缀，其长度为它们之间的height值的最小值。而我们分组之后，每组后缀之间height值的最小值大于等于k。所以，后缀数大于1的分组中，有可能存在满足题目限制条件的长度不小于k的子串。只要判断满足题目限制条件成立，那么说明存在长度至少为k的合法子串。

对于本题，限制条件是不重叠，判断的方法是，一组后缀中，起始位置最大的后缀的起始位置减去起始位置最小的后缀的起始位置>=k。满足这个条件的话，那么这两个后缀的公共前缀不但出现两次，而且出现两次的起始位置间隔大于等于k，所以不会重叠。

深刻理解这种height分组方法以及判断重叠与否的方法，在后面的问题中起到举足轻重的作用。

5、最长的出现k次的重复（可重叠）子串。 PKU3261

使用后缀数组解题时，遇到“最长”，除了特殊情况外（如问题3），一般需要二分答案，利用height值进行分组。本题的限制条件为出现k次。只需判断，有没有哪一组后缀数量不少于k就可以了。相信有了我前面问题的分析作为基础，这个应该不难理解。注意理解“不少于k次”而不是“等于k次”的原因。如果理解不了，可以找个具体的例子来分析分析。

6、最长回文子串 ural1297

这个问题没有很直接的方法可以解决，但可以采用枚举的方法。具体的就是枚举回文子串的中心所在位置i。注意要分回文子串的长度为奇数还是偶数两种情况分析。然后，我们要做的，是要求出以i为中心的回文子串最长为多长。利用后缀数组，可以设计出这样一种求法：求i往后的后缀与i往前的前缀的最长公共前缀。我这里的表述有些问题，不过不影响理解。

要快速地求这个最长前缀，可以将原串反写之后接在原串后面。在使用后缀数组的题目中，连接两个（n个）字符串时，中间要用不可能会出现在原串中，不一样的非0号的字符将它们隔开。这样可以做到不影响后缀数组的性质。然后，问题就可以转化为求两个后缀的最长公共前缀了。具体的细节，留给大家自己思考...（懒...原谅我吧，都打这么多字了..一个多小时了啊TOT）

7、求一个串最多由哪个串复制若干次得到 PKU2406

具体的问题描述请参考PKU2406.这个问题可以用KMP解决，而且效率比后缀数组好。

利用后缀数组直接解决本题也很困难（主要是，就算二分答案，也难以解决转变而成的判定性问题。上题也是），但可以同过枚举模板串的长度k（模板串指被复制的那个串）将问题变成一个后缀数组可以解决的判定性问题。首先判断k能否被n整除，然后只要看lcp(1,k+1)（实际在用c写程序时是lcp(0,k)）是否为n-k就可以了。

为什么这样就行了呢？这要充分考虑到后缀的性质。当lcp（1，k+1）=n-k时，后缀k+1是后缀1（即整个字符串）的一个前缀。（因为后缀k+1的长度为n-k）那么，后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。而后缀1的第k+1..2k个字符，又相当于后缀k+1的前k个字符，所以与后缀1的前k个字符对应相同，且和后缀k的k+1..2k又对应相同。依次类推，只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值，就可以得到n/k的最大值了。

8、求两个字符串的最长公共子串。Pku2774、Ural1517

首先区分好“最长公共子串”和“最长公共子序列”。前者的子串是连续的，后者是可以不连续的。

对于两个字符串的问题，一般情况下均将它们连起来，构造height数组。然后，最长公共子串问题等价于后缀的最长公共前缀问题。只不过，并非所有的lcp值都能作为问题的答案。只有当两个后缀分属两个字符串时，它们的lcp值才能作为答案。与问题3一样，本题的答案必然是某个height值，因为lcp值是某段height值中的最小值。当区间长度为1时，lcp值等于某个height值。所以，本题只要扫描一遍后缀，找出后缀分属两个字符串的height值中的最大值就可以了。判断方法这里就不说明了，留给大家自己思考...

9、重复次数最多的重复子串 SPOJ 687，Pku3693

难度比较大的一个问题，主要是罗穗骞的论文里的题解写得有点含糊不清。题目的具体含义可以去参考Pku3693.

又是一题难以通过二分枚举答案解决的问题（因为要求的是重复次数），所以选择朴素枚举的方法。先枚举重复子串的长度k，再利用后缀数组来求长度为k的子串最多重复出现多少次。注意到一点，假如一个字符串它重复出现2次（这里不讨论一次的情况，因为那是必然的），那么它必然包含s[0],s[k],s[2*k]...之中的相邻的两个。所以，我们可以枚举一个数i，然后判断从i*k这个位置起的长度为k的字符串能重复出现多少次。判断方法和8中的相似，lcp(i*k,(i+1)*k)/k+1。但是，仅仅这样会忽略点一些特殊情况，即重复子串的起点不在[i*k]位置上时的情况。这种情况应该怎么求解呢？看下面这个例子：

aabababc

当k=2，i=1时，枚举到2的位置，此时的重复子串为ba(注意第一位是0),lcp(2，4)=3，所以ba重复出现了2次。但实际上，起始位置为1的字符串ab出现次数更多，为3次。我们注意到，这种情况下，lcp(2,4)=3，3不是2的整数倍。说明当前重复子串在最后没有多重复出现一次，而重复出现了部分（这里是多重复出现了一个b）。如果我这样说你没有看懂，那么更具体地：

sa[2]=bababc

sa[4]=babc

lcp=bab

现在注意到了吧，ba重复出现了两次之后，出现了一个b，而a没有出现。那么，不难想到，可以将枚举的位置往前挪一位，这样这个最后的b就能和前面的一个a构成一个重复子串了，而假如前挪的一位正好是a，那么答案可以多1。所以，我们需要求出a=lcp(i*k,(i+1)*k)%n，然后向前挪k-a位，再用同样的方法求其重复出现的长度。这里，令b=k-a,只需要lcp(b,b+k)>=k就可以了。实际上，lcp(b,b+k)>=k时，lcp(b,b+k)必然大于等于之前求得的lcp值，而此时答案的长度只加1。没有理解的朋友细细体会下上图吧。

10.多个串的公共子串问题 PKU3294

首先将串连接起来，然后构造height数组，然后怎么办呢？

对，二分答案再判断是否可行就行了。可行条件很直观：有一组后缀，有超过题目要求的个数个不同的字符串中的后缀存在。即，假如题目要求要出现在至少k个串中，那么就得有一组后缀，在不同字符串中的后缀数大于等于k。

11、出现或反转后出现所有字符串中的最长子串 PKU1226
12、不重叠地至少两次出现在所有字符串中的最长子串
之所以把两题一起说，因为它们大同小异，方法在前面的题目均出现过。对于多个串，连起来；反转后出现，将每个字符串反写后和原串都连起来，将反写后的串和原串看成同一个串；求最长，二分答案后height分组；出现在所有字符串中（反写后的也行），判断方法和10一样，k=n而已；不重叠见问题4，只不过这里对于每个字符串都要进行检验而已。

13、两个字符串的重复子串个数。 Pku3415

我个人觉得颇有难度的一个问题。具体的题目描述参看Pku3415。

14、最后的总结

用后缀数组解题有着一定的规律可循，这是后缀的性质所决定的，具体归纳如下：

1、N个字符串的问题（N>1）

方法：将它们连接起来，中间用不会出现在原串中的，互不相同的，非0号字符分隔开。

2、无限制条件下的最长公共子串（重复子串算是后缀们的最长公共前缀）

方法：height的最大值。这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串，才可以直接是height的最大值。

3、特殊条件下的最长子串

方法：二分答案，再根据height数组进行分组，根据条件完成判定性问题。三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为len，特殊条件有：

3.1、出现在k个串中

条件：属于不同字符串的后缀个数不小于k。（在一组后缀中，下面省略）

3.2、不重叠

条件：出现在同一字符串中的后缀中，出现位置的最大值减最小值大于等于len。

3.3、可重叠出现k次

条件：出现在同一字符串中的后缀个数大于等于k。若对于每个字符串都需要满足，需要逐个字符串进行判断。

4、特殊计数

方法：根据后缀的性质，和题目的要求，通过自己的思考，看看用后缀数组能否实现。一般和“子串”有关的题目，用后缀数组应该是可以解决的。

5、重复问题

知道一点：lcp(i,i+k)可以判断，以i为起点，长度为k的一个字符串，它向后自复制的长度为多少，再根据具体题目具体分析，得出算法即可。