什么是后缀数组?

假设我们现在有一个字符串”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

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

发表评论

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