后缀数组学习小记 (模板)

爱被打了一巴掌 2022-08-24 01:25 161阅读 0赞

# 学习资料及参考文章： #

[后缀数组及其应用.ppt - 豆丁网][.ppt -]

[后缀数组--许智磊\_百度文库][--]

[国家集训队2004论文集\_许智磊(后缀数组)\_百度文库][2004]

[后缀数组——处理字符串的有力工具\_百度文库][Link 1]

[后缀数组两种算法的分析比较 - Localhost 8080 - C++博客][- Localhost 8080 - C]

# 基本定义及性质 #

LCP(Longest Common Prefix)：最长公共前缀

后缀数组 sa\[i\] : 表示排在第i位的后缀 起始下标

名次数组 rank\[i\] : 表示后缀 suffix(i)排在第几

简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？

后缀数组和名次数组为互逆运算：设Rank\[i\]=j，则SA\[j\]=i。

性质 1 LCP(i,j)=LCP(j,i)  
性质 2 LCP(i,i)=len(Suffix(SA\[i\]))=n-SA\[i\]+1

height数组：height\[i\]=suffix(sa\[i-1\])和suffix(sa\[i\])的最长公共前缀(LCP)，也就是排名相邻的两个后缀的最长公共前缀。

对于j和k，不妨设rank\[j\]<rank\[k\]，则有以下性质：  
suffix(j)和suffix(k)的最长公共前缀为height\[rank\[j\]+1\]，height\[rank\[j\]+2\]，height\[rank\[j\]+3\]，……，height\[rank\[k\]\]中的最小值。

h\[i\]: 表示 suffix(i)与其排名前一位的 LCP值

h数组：h\[i\]=height\[rank\[i\]\]，即 height\[i\]=h\[SA\[i\]\]  
h数组的性质：h\[i\]>=h\[i-1\]-1。

实际实现时通常不储存h数组。

RMQ问题：区间最值的问题

具体可参考 [RMQ的ST算法学习小记 Poj 3264 Balanced Lineup - whyorwhnt的专栏][RMQ_ST_ Poj 3264 Balanced Lineup - whyorwhnt]

构造后缀数组有两种主流算法：

倍增算法(Doubling Algorithm)

DC3算法(Difference Cover mod 3)

时间复杂度：

倍增算法的时间复杂度为O(nlogn)，DC3算法的时间复杂度为O(n)。

DC3渐进时间复杂度比较小，但是常数项比较大。

空间复杂度：

倍增算法和DC3算法的空间复杂度都是O(n)。按前面所讲的实现方法，倍增算法所需数组总大小为6n，DC3算法所需数组总大小为10n。

在DC3算法中，rank和sa数组需要开3倍大小，为了递归处理时不用每次都申请新的内存空间。

具体区别请参考上述文章关于两种方法的对比。

以前做练习时我用的都是DA，但2014北京邀请赛在题目重现时卡掉了O(nlogn)的DA算法，考虑到实际比赛时对空间的限制相对宽松，所以以后准备使用DC3算法。

# 其他人的总结及模板 #

[后缀数组专题与代码模板 - yefeng1627 - 博客园][- yefeng1627 -]

[【总结】后缀数组 - DrunBee - 博客园][- DrunBee -]

倍增算法，个人常用版：

const int N = int(2e5)+10;
    
    int cmp(int *r,int a,int b,int l){
    	return (r[a]==r[b]) && (r[a+l]==r[b+l]);
    }
    int wa[N],wb[N],ws[N],wv[N];
    int rank[N],height[N],sa[N];
    
    void DA(int *r,int *sa,int n,int m){
    	int i,j,p,*x=wa,*y=wb,*t;
    	for(i=0;i<m;i++) ws[i]=0;
    	for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    	for(i=1;i<m;i++) ws[i]+=ws[i-1];
    	for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    	for(j=1,p=1;p<n;j*=2,m=p)
    	{
    		for(p=0,i=n-j;i<n;i++) y[p++]=i;
    		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
    		for(i=0;i<n;i++) wv[i]=x[y[i]];
    		for(i=0;i<m;i++) ws[i]=0;
    		for(i=0;i<n;i++) ws[wv[i]]++;
    		for(i=1;i<m;i++) ws[i]+=ws[i-1];
    		for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
    		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
    			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    		//printf("p = %d\n", p );
    	}
    }
    void calheight(int *r,int *sa,int n){
    //	memset(height,0,sizeof(height));
    //	memset(rank,0,sizeof(rank));
    	int i,j,k=0;
    	for(i=1;i<=n;i++) rank[sa[i]]=i;
    	for(i=0;i<n; height[rank[i++]] = k )
    	for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    }

本段的第一篇参考文献里有带简单注释的版本

这里有一份详细分析，带详细的注释： [后缀数组学习笔记——罗穗骞倍增算法代码 - Staginner - 博客园][- Staginner -]

论文附件中的倍增算法完整代码：

#define maxn 1000001
    int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
    int cmp(int *r,int a,int b,int l)
    {return r[a]==r[b]&&r[a+l]==r[b+l];}
    void da(int *r,int *sa,int n,int m)
    {
         int i,j,p,*x=wa,*y=wb,*t;
         for(i=0;i<m;i++) ws[i]=0;
         for(i=0;i<n;i++) ws[x[i]=r[i]]++;
         for(i=1;i<m;i++) ws[i]+=ws[i-1];
         for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
         for(j=1,p=1;p<n;j*=2,m=p)
         {
           for(p=0,i=n-j;i<n;i++) y[p++]=i;
           for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
           for(i=0;i<n;i++) wv[i]=x[y[i]];
           for(i=0;i<m;i++) ws[i]=0;
           for(i=0;i<n;i++) ws[wv[i]]++;
           for(i=1;i<m;i++) ws[i]+=ws[i-1];
           for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
           for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
           x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
         }
         return;
    }
    int rank[maxn],height[maxn];
    void calheight(int *r,int *sa,int n)
    {
         int i,j,k=0;
         for(i=1;i<=n;i++) rank[sa[i]]=i;
         for(i=0;i<n;height[rank[i++]]=k)
         for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
         return;
    }
    int RMQ[maxn];
    int mm[maxn];
    int best[20][maxn];
    void initRMQ(int n)
    {
         int i,j,a,b;
         for(mm[0]=-1,i=1;i<=n;i++)
         mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
         for(i=1;i<=n;i++) best[0][i]=i;
         for(i=1;i<=mm[n];i++)
         for(j=1;j<=n+1-(1<<i);j++)
         {
           a=best[i-1][j];
           b=best[i-1][j+(1<<(i-1))];
           if(RMQ[a]<RMQ[b]) best[i][j]=a;
           else best[i][j]=b;
         }
         return;
    }
    int askRMQ(int a,int b)
    {
        int t;
        t=mm[b-a+1];b-=(1<<t)-1;
        a=best[t][a];b=best[t][b];
        return RMQ[a]<RMQ[b]?a:b;
    }
    int lcp(int a,int b)
    {
        int t;
        a=rank[a];b=rank[b];
        if(a>b) {t=a;a=b;b=t;}
        return(height[askRMQ(a+1,b)]);
    }
    int main()
    {
    	char s[10];
    	int n,m=0,i,l,r[10],sa[10];
    	scanf("%s",s);
    	l=strlen(s);
    	for(i=0;i<l;i++)
    	{
    		r[i]=s[i];
    		if(s[i]>m)
    			m=s[i];
    	}
    	r[9]=0;
    	da(r,sa,10,m);
    	return 0;
    }

DC3 个人常用模板

const int N = int(1e3)+10;
    
    #define F(x) ((x)/3+((x)%3==1?0:tb))
    #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
    
    int wa[N],wb[N],wv[N],ws[N];
    int c0 (int *r,int a,int b){
    	return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
    }
    int c12 (int k,int *r,int a,int b){
    	if (k==2) return r[a]<r[b] || r[a]==r[b] && c12(1,r,a+1,b+1);
    	else return r[a]<r[b] || r[a]==r[b] && wv[a+1]<wv[b+1];
    }
    void sort (int *r,int *a,int *b,int n,int m){
    	int i;
    	for(i=0;i<n;i++) wv[i]=r[a[i]];
    	for(i=0;i<m;i++) ws[i]=0;
    	for(i=0;i<n;i++) ws[wv[i]]++;
    	for(i=1;i<m;i++) ws[i]+=ws[i-1];
    	for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
    }
    void DC3 (int *r,int *sa,int n,int m){
    	int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    	r[n]=r[n+1]=0;
    	for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
    	sort(r+2,wa,wb,tbc,m);
    	sort(r+1,wb,wa,tbc,m);
    	sort(r,wa,wb,tbc,m);
    	for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
    		rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    	if(p<tbc) DC3(rn,san,tbc,p);
    	else for(i=0;i<tbc;i++) san[rn[i]]=i;
    	for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    	if(n%3==1) wb[ta++]=n-1;
    	sort(r,wb,wa,ta,m);
    	for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
    	for(i=0,j=0,p=0;i<ta && j<tbc;p++)
    		sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    	for(;i<ta;p++) sa[p]=wa[i++];
    	for(;j<tbc;p++) sa[p]=wb[j++];
    }  
    int rank[N],height[N],sa[3*N],data[3*N];
    
    void calheight(int *r,int *sa,int n){
    //	memset(height,0,sizeof(height));
    //	memset(rank,0,sizeof(rank));
    	int i,j,k=0;
    	for(i=1;i<=n;i++) rank[sa[i]]=i;
    	for(i=0;i<n; height[rank[i++]] = k )
    	for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    }

DC3网上的分析注释： [DC3算法理解记录\_success\_新浪博客][DC3_success]

论文附件中的DC3算法完整代码：

#define maxn 1000003
    #define F(x) ((x)/3+((x)%3==1?0:tb))
    #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
    int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
    int c0(int *r,int a,int b)
    {return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
    int c12(int k,int *r,int a,int b)
    {if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
     else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}
    void sort(int *r,int *a,int *b,int n,int m)
    {
         int i;
         for(i=0;i<n;i++) wv[i]=r[a[i]];
         for(i=0;i<m;i++) ws[i]=0;
         for(i=0;i<n;i++) ws[wv[i]]++;
         for(i=1;i<m;i++) ws[i]+=ws[i-1];
         for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
         return;
    }
    void dc3(int *r,int *sa,int n,int m)
    {
         int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
         r[n]=r[n+1]=0;
         for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
         sort(r+2,wa,wb,tbc,m);
         sort(r+1,wb,wa,tbc,m);
         sort(r,wa,wb,tbc,m);
         for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
         rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
         if(p<tbc) dc3(rn,san,tbc,p);
         else for(i=0;i<tbc;i++) san[rn[i]]=i;
         for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
         if(n%3==1) wb[ta++]=n-1;
         sort(r,wb,wa,ta,m);
         for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
         for(i=0,j=0,p=0;i<ta && j<tbc;p++)
         sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
         for(;i<ta;p++) sa[p]=wa[i++];
         for(;j<tbc;p++) sa[p]=wb[j++];
         return;
    }
    int rank[maxn],height[maxn];
    void calheight(int *r,int *sa,int n)
    {
         int i,j,k=0;
         for(i=1;i<=n;i++) rank[sa[i]]=i;
         for(i=0;i<n;height[rank[i++]]=k)
         for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
         return;
    }
    int RMQ[maxn];
    int mm[maxn];
    int best[20][maxn];
    void initRMQ(int n)
    {
         int i,j,a,b;
         for(mm[0]=-1,i=1;i<=n;i++)
         mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
         for(i=1;i<=n;i++) best[0][i]=i;
         for(i=1;i<=mm[n];i++)
         for(j=1;j<=n+1-(1<<i);j++)
         {
           a=best[i-1][j];
           b=best[i-1][j+(1<<(i-1))];
           if(RMQ[a]<RMQ[b]) best[i][j]=a;
           else best[i][j]=b;
         }
         return;
    }
    int askRMQ(int a,int b)
    {
        int t;
        t=mm[b-a+1];b-=(1<<t)-1;
        a=best[t][a];b=best[t][b];
        return RMQ[a]<RMQ[b]?a:b;
    }
    int lcp(int a,int b)
    {
        int t;
        a=rank[a];b=rank[b];
        if(a>b) {t=a;a=b;b=t;}
        return(height[askRMQ(a+1,b)]);
    }

# 关于单个字符串的基础题目总结 #

本文只列出做过的有关单个子串的基础题目，有关后缀数组的一些技巧性使用，公共子串问题，与RMQ问题结合的问题将在之后的博文中总结

### 可重叠最长重复子串 ###

根据 height\[i\] = LCP\{ suffix( sa\[i-1\] ), suffix( sa\[i\] ) \} ，最长重复可重叠子串长度是 Max\{ height\[i\] \}

### 不可重叠最长重复子串 ###

[Poj 1743 Musical Theme (后缀数组 不可重叠最长重复子串) - whyorwhnt的专栏][Poj 1743 Musical Theme _ _ - whyorwhnt]

### 至少重叠k次最长重复子串 ###

[POJ 3261 Milk Patterns (离散化+后缀数组 可重叠k次最长重复子串) - whyorwhnt的专栏][POJ 3261 Milk Patterns _ _k_ - whyorwhnt]

下面这题要求给出最后出现的位置

[Hdu 4080 & Poj 3882 Stammering Aliens (后缀数组 可重叠k次最长重复子串) - whyorwhnt的专栏][Hdu 4080 _ Poj 3882 Stammering Aliens _ _k_ - whyorwhnt]

### 出现2次及以上且不重叠的子串的个数 ###

[Hdu 3518 Boring counting (出现2次及以上且不重叠的子串的个数) - whyorwhnt的专栏][Hdu 3518 Boring counting _2_ - whyorwhnt]

### 子串的个数 ###

[SPOJ 694 Distinct Substrings + SPOJ 705 New Distinct Substrings (可重叠不相同子串个数) - whyorwhnt的专栏][SPOJ 694 Distinct Substrings _ SPOJ 705 New Distinct Substrings _ - whyorwhnt]

### 区间长度子串个数 ###

[LightOJ 1314 Names for Babies (后缀数组 区间长度子串个数) - whyorwhnt的专栏][LightOJ 1314 Names for Babies _ _ - whyorwhnt]

[.ppt -]: http://www.docin.com/p-511958000.html
[--]: http://wenku.baidu.com/link?url=A2_dodCPqlDAeGVQKNx_yQoS-TqzJv-BDAy43MDwwzStUQ33kvrg22-TiK2JsFcUN-i6x3Pwsd3bjm9KjQmW1RPHIBLfp696eHP6m8hI4NO
[2004]: http://wenku.baidu.com/link?url=AleQv9CeZSj53CQa1gAiBsJKO60mIgpkncKuMRA43ZQoRPDPFGMoyAEUs9BPKrWO6ldyCmbKWU9aEgFmdgY4RCcg_ACXUGc3HacSgdZy4We
[Link 1]: http://wenku.baidu.com/link?url=1kyJDd9t21ExQh6n8sDuJciqa-ssIKhxq3CHe8xLoEc2P9aJQqhtQU3dUOowIYjbkpDJrIAn7EaAej4VVaqeQEgoVIRJhpu3rvPASGbGq0m
[- Localhost 8080 - C]: http://www.cppblog.com/superKiki/archive/2010/05/15/115421.html
[RMQ_ST_ Poj 3264 Balanced Lineup - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/17721935
[- yefeng1627 -]: http://www.cnblogs.com/yefeng1627/archive/2013/08/02/3233611.html
[- DrunBee -]: http://www.cnblogs.com/DrunBee/archive/2012/07/11/2572298.html
[- Staginner -]: http://www.cnblogs.com/staginner/archive/2012/02/02/2335600.html
[DC3_success]: http://blog.sina.com.cn/s/blog_79dfe12701017566.html
[Poj 1743 Musical Theme _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9749467
[POJ 3261 Milk Patterns _ _k_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9771673
[Hdu 4080 _ Poj 3882 Stammering Aliens _ _k_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9857463
[Hdu 3518 Boring counting _2_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9857911
[SPOJ 694 Distinct Substrings _ SPOJ 705 New Distinct Substrings _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9771595
[LightOJ 1314 Names for Babies _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9860559