后缀数组

2014.12.08 10:51 Mon| 20 visits oi_2015| 2015_算法笔记| Text

orz wyfcyx

我是又一个被刘汝佳坑了的孩子 T^T

后缀数组

将一个字符串的所有后缀按照字典序从小到大排序,记 $sa[i]$ 表示排名第 $i$ 的后缀在原串的位置。(均从 $0$ 开始标号)

后缀数组是处理字符串问题的一种有效工具,能够挖掘出字符串最深处的性质

——wyfcyx

求解后缀数组

朴素模拟

不难想到直接调用快速排序算法给所有后缀排序,然而比较两个字符串的时间复杂度最坏可达 $\mathcal O(n)$ 。因此,在最坏情况下,总时间复杂度可能会达到 $\mathcal O(n^2 \log n)$ 。

理论上,这种算法无法应对长度动辄为 $10^5$ 的字符串,但是若串是随机的话,期望比较次数为 $\mathcal O(1)$ 。在一些情况下可以使用。

倍增算法

进行 $k$ 次排序,对于第 $k$ 次排序,比较的是 $n$ 个后缀仅考虑前 $\mathcal O(n)$ 个字符时的顺序

考虑在第 $k$ 次排序时,我们在之前已经把每连续 $2^{k-1}$ 个字符都排好了序,那么前 $2^k$ 个字符显然可以看成是一个包含有两个长度为 $2^{k-1}$ 的字串的二元组!从而,我们只需对这些二元组排序即可!

排好序之后对这些二元组进行重标号,作为前 $2^k$ 个字符的顺序,同时以便于下一次的排序。

重复进行上述操作,直到得到的标号互不相同,算法结束。

利用倍增思想,我们只需要进行 $\mathcal O(\log n)$ 次排序。若对于每一次排序操作都使用快速排序只有重标号,则总时间复杂度为 $\mathcal O(n \log ^2 n)$ 。而利用基数排序这一号称线性排序的算法,总时间复杂度仅有 $\mathcal O(n \log n)$ 。

实际上,虽然存在时间复杂度更低的算法,但由于在解题过程中常常伴随其他时间复杂度更大的操作,基于基数排序的倍增算法以其代码量小的优势在算法竞赛中更为常见。

DC3算法

利用DC3算法可以在 $\mathcal O(n)$ 的时间内快速求解后缀数组,但是其在实际应用中并不比倍增算法更有价值。

后缀数组的扩展

在实际应用中,常常需要求出以下两个辅助数组来解决问题:

rank数组

$rank[i]$ 表示开头位置为i的后缀的排名。

只需求出 $sa$ 数组后进行简单映射即可求出。时间复杂度 $\mathcal O(n)$ 。

height数组

$height[i] \dots (1≤i<n)$ 表示排名为i的后缀和排名为 $i-1$ 的后缀的最长公共前缀(Longest Common Prefix)的长度。

对于两个后缀 $j$ , $k$ ,不妨令 $rank[j]<rank[k]$ ,则两个后缀的LCP等于 $\min _{i=rank[j]+1} ^{rank[k]} height[i]$ 。而这个可以利用RMQ快速得到。

对于求解 $height$ 数组,可以根据性质 $height[rank[i]] \ge height[rank[i-1]]-1$ ,利用单调性在 $\mathcal O(n)$ 的时间内得出。

关于这一性质的证明如下:

设 $k=sa[rank[i-1]-1]$ ,则 $height[rank[i-1]]$ 表示后缀 $i-1$ 和后缀 $k$ 之间的LCP。在它们的基础上同时去掉一个字符,则后缀 $k+1$ 必然排在后缀 $i$ 前,且两者LCP不小于 $height[rank[i-1]]-1$ 。由此可知 $\min _{i=rank[k+1]+1} ^{rank[i]} height[i] \ge height[rank[i-1]]-1$ ,则 $height[rank[i]] \ge height[rank[i-1]]-1$ 。

代码实现

后缀数组倍增算法+height

#include <bits/stdc++.h>
using namespace std;
#define N 200005

char str[N];
int n,c[N],x[N],y[N],sa[N],rank[N],height[N];

inline bool same(int a,int b,int k)
{
    return y[a]==y[b] && ((a+k>=n&&b+k>=n)||(a+k<n&&b+k<n&&y[a+k]==y[b+k]));
}

void get_sa(int m=256)
{
    for(int i=0;i<n;i++) c[x[i]=str[i]]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<n;k<<=1)
    {
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        memset(c,0,m*sizeof(int));
        for(int i=0;i<n;i++) c[x[y[i]]]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        for(int i=0;i<n;i++) y[i]=x[i];
        m=0; x[sa[0]]=0;
        for(int i=1;i<n;i++)
            x[sa[i]]=same(sa[i-1],sa[i],k)?m:++m;
        if(++m==n) break;
    }
}

void get_height()
{
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0,j,k=0;i<n;height[rank[i++]]=k)
        if(rank[i]) for(k?k--:0,j=sa[rank[i]-1];str[i+k]==str[j+k];k++);
}

int main()
{
    scanf("%s",str);
    n=strlen(str);
    get_sa();
    get_height();
    for(int i=0;i<n;i++)
        printf("%d%c",sa[i]+1,i==n-1?'\n':' ');
    for(int i=1;i<n;i++)
        printf("%d%c",height[i],i==n-1?'\n':' ');
    return 0;
}

后缀数组DC3算法

//by wyfcyx
//据wyf说,这个模板里面有一个bug,慎用!

#include <bits/stdc++.h>
using namespace std;
#define N 200010

char s[N];
int v[N*3],sa[N*3],qa[N],qb[N];

inline bool cmp1(int*v,int a,int b){
    return v[a]==v[b]&&v[a+1]==v[b+1]&&v[a+2]==v[b+2];
}
int sav[N];
inline bool cmp2(int d,int*v,int a,int b){
    if(d==1)return v[a]<v[b]||(v[a]==v[b]&&sav[a+1]<sav[b+1]);
    else return v[a]<v[b]||(v[a]==v[b]&&cmp2(1,v,a+1,b+1));
}
inline void RadixSort(int*v,int*q,int*sa,int n,int m){
    static int c[N];int i;
    for(i=0;i<m;++i)c[i]=0;
    for(i=0;i<n;++i)++c[v[q[i]]];
    for(i=1;i<m;++i)c[i]+=c[i-1];
    for(i=n-1;i>=0;--i)sa[--c[v[q[i]]]]=q[i];
}
#define f(x) ((x)%3==1?(x)/3:(x)/3+na)
#define rf(x) ((x)<na?3*(x)+1:3*((x)-na)+2)
void dc3(int*v,int*sa,int n,int m){
    int i,j,k,*nv=v+n+3,*nsa=sa+n+3,na=(n+2)/3,nbc=0,lab;
    v[n]=v[n+1]=v[n+2]=0;
    for(i=0;i<n;++i)if(i%3)qa[nbc++]=i;if(n%3==1)qa[nbc++]=n;
    RadixSort(v+2,qa,qb,nbc,m);
    RadixSort(v+1,qb,qa,nbc,m);
    RadixSort(v,qa,qb,nbc,m);
    for(i=lab=0;i<nbc;++lab,i=j+1){
        for(j=i;j<nbc-1&&cmp1(v,qb[j],qb[j+1]);++j);
        for(k=i;k<=j;++k)nv[f(qb[k])]=lab;
    }
    if(lab<nbc)dc3(nv,nsa,nbc,lab);
    else for(i=0;i<nbc;++i)nsa[nv[i]]=i;
    for(i=j=0;i<nbc;++i)if(nsa[i]<na)qb[j++]=3*nsa[i];
    RadixSort(v,qb,qa,na,m);
    for(i=0;i<nbc;++i)sav[qb[i]=rf(nsa[i])]=i;
    for(i=lab=0,j=(n%3==1);i<na&&j<nbc;)
        sa[lab++]=cmp2(qb[j]%3,v,qa[i],qb[j])?qa[i++]:qb[j++];
    while(i<na)sa[lab++]=qa[i++];
    while(j<nbc)sa[lab++]=qb[j++];
}

int main(){
    scanf("%s",s);int len=strlen(s);
    register int i,j;for(i=len;i<2*len;++i)s[i]=s[i-len];len*=2;
    for(i=0;i<len;++i)v[i]=s[i];
    dc3(v,sa,len,256);
    for(i=0;i<len;++i)if(sa[i]<len/2)putchar(s[sa[i]+len/2-1]);
    return 0;
}