什么是后缀数组?

假设我们现在有一个字符串”ababa”
我们知道这个数组有一些后缀,分别是(以下后缀i指以i为开头的后缀)

1 2 3 4 5
ababa baba aba ba a

现在我们按照字典序将它们排序,得到:5 3 1 4 2,那么我们令$SA_1=5,SA_2=3,SA_3=1…$便得到了后缀数组SA

如何求后缀数组?

给一道例题:洛谷P3809
主要思想是倍增,可以结合图,文字说明和代码进行查看。
后缀数组
假设现在我们已经排序完成了所有长度为num的子串,并得到了当前子串们的SA(排完序后的顺序)和$x_i$(又称rank,即以i开头的子串的排名)
现在我们的任务是排序所有长度为num+num的子串,那么,我们令一个这样的子串由两个长度为num的子串A和B组成。现在,我们的任务是以A为第一关键字,B为第二关键字进行基数排序
定义$y_i$:第二关键字排名为i的子串开头的位置,以下步骤是求出$y_i$:

1.对于末尾溢出的子串,它们的第二关键字为0,对它们进行处理。
2.对于所有长度为num的子串,如果它们的开头大于num,则可以作为一个长度为num+num的子串的第二关键字,然后根据它们的SA来求一些$y_i$


        km=0;
        for(int i=n-num+1;i<=n;++i) y[++km]=i;
        for(int i=1;i<=n;++i) if(SA[i]>num) y[++km]=SA[i]-num;

然后,求出新的SA值。

1.开一个桶T,将每个关键字2对应的关键字1塞进桶里。
2.利用每个关键字2对应的关键字1的排名,更新SA(即基数排序)


void Rsort() {
    for(int i=0;i<=m;++i) T[i]=0;
    for(int i=1;i<=n;++i) ++T[x[y[i]]];//y:关键字2->子串开头,x:子串开头->关键字1
    for(int i=1;i<=m;++i) T[i]+=T[i-1];
    for(int i=n;i>=1;--i) SA[T[x[y[i]]]--]=y[i];
    //从后往前。因为关键字2已经排序了,而每次-1,是从大到小确定排名为T[x[y[i]]]的子串开头
}

最后,求出新的$x_i$。这个只要利用SA就行了,同时还要利用上一次的$x_i$,用于对比两个子串是否相同,进行去重。
由于子串长度溢出末尾就补0这个操作,所以最后一次我们排序的n个子串一定是所有后缀了。
完整代码实现就是:


#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
char s[N];
int n,m,a[N],SA[N],x[N],y[N],T[N];
void Rsort() {
    for(int i=0;i<=m;++i) T[i]=0;
    for(int i=1;i<=n;++i) ++T[x[y[i]]];
    for(int i=1;i<=m;++i) T[i]+=T[i-1];
    for(int i=n;i>=1;--i) SA[T[x[y[i]]]--]=y[i];
}
int cmp(int i,int j,int num) {return y[i]==y[j]&&y[i+num]==y[j+num];}
void getSA() {
    for(int i=1;i<=n;++i) x[i]=a[i],y[i]=i;
    m=127,Rsort();//m:当前有多少种排名
    for(int km=1,num=1;km<n;num+=num,m=km) {//如果当前生成的排名数量有n个以上,那么排完了
        km=0;
        for(int i=n-num+1;i<=n;++i) y[++km]=i;
        for(int i=1;i<=n;++i) if(SA[i]>num) y[++km]=SA[i]-num;
        Rsort(),swap(x,y),x[SA[1]]=km=1;//用y暂存x的值用于比较
        for(int i=2;i<=n;++i) x[SA[i]]=cmp(SA[i],SA[i-1],num)?km:++km;
    }
}
int main()
{
    scanf("%s",s),n=strlen(s);
    for(int i=0;i<n;++i) a[i+1]=s[i]-' ';
    getSA();for(int i=1;i<=n;++i) printf("%d ",SA[i]);
    return 0;
}

后缀的最长前缀

$Height_i$:排名为i和i-1的两个后缀的最长公共前缀
$H_i$:后缀i和排名在其前面的后缀的最长公共前缀
我们可以证明一个性质:$H_i \geq H_{i-1}-1$
假设后缀k是后缀i-1的前一名,最长前缀就是$H_{i-1}$,去掉一个字符,变成了后缀k+1和后缀i。
如果$H_{i-1}$等于0或1,$H_i \geq 0$显然成立
否则,k+1一定是i的前一名,则$H_{i-1} – 1 \leq H_i$
于是我们可以O(n)计算$Height_i$啦!


void getHei() {
    int lcp=0;
    for(int i=1;i<=n;++i) {
        if(lcp) --lcp;
        int j=SA[x[i]-1];
        while(a[j+lcp]==a[i+lcp]&&lcp<n) ++lcp;
        Hei[x[i]]=lcp;
    }
}

后缀数组的基本应用

洛谷P2408:每一个子串必定是一个后缀的前缀。我们把后缀i与后缀i-1的公共前缀看作是后缀i独有的子串,那么答案就是$\sum_i^n (n-SA_i+1-Height_i)$

bzoj1717/洛谷P2852:二分答案ans。如果在Height数组中,连续的大于等于ans的数大于等于K-1个(因为K-1个Height对应K个子串嘛),说明当前答案可行,否则不可行。

bzoj1692/洛谷P2870:比较从队首与队尾的字母字典序大小,如果一样,就要依次比较。所以干脆将原串翻转过来粘在后面,然后求这个长度为2n的新串的后缀数组,依次贪心比较获得答案。

spoj220:把所有的串粘在一起,中间用不同的特殊字符隔开(这样简单方便一些)。二分答案ans,扫描Height数组,提取其中$Height_i \geq ans$的区间[l,r],对于所有i属于$[SA_{l-1},SA_r]$,是否其中在每个字符串中最小和最大的之间相差大于等于ans,如果是,则该答案为合法。

bzoj2258/poj2758:题解戳我

HDU3948:把字符串改成跑manacher要用的形式,然后用manacher搞出每一个字符向左和右可以得到的回文长度p,再求出字符串的SA和Height。然后每个字符造成的贡献是$(p[SA_i]-min(Height_i,p[SA_{last}]))/2$,这个last是指,如果以某个字符为中心的回文串,被完全包括在了上一个字符为中心的回文串中,那么就跳过这个字符,用这种方式得到的上一个字符。

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *