后缀数组 模板(结构体) DC3 与倍增

DC3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e6+7;

struct suffix_array{
    int str[M],sa[M],rank[M],t1[M],t2[M],c[M];
    //int lg2[M];int rmq[21][M],height[M];
    //sa[i],排名i(1-n)后缀的起始下标(0 - n-1)
    //rank[i],下标i(0 - n-1)后缀的排名(1 - n) 
    bool cmp(int *r,int a,int b,int l){
        return r[a]==r[b]&&r[a+l]==r[b+l];
    }
    void gao(int n,int m){
    	str[n]=0;
        n++; int i, j, p, *x = t1, *y = t2;
        for(i=0;i<m;++i) c[i]=0;
        for(i=0;i<n;++i) c[x[i]=str[i]]++;
        for(i=1;i<m;++i) c[i]+=c[i-1];
        for(i=n-1;i>=0;--i) sa[--c[x[i]]]=i;
        for(j=1;j<n;j<<=1){
            p=0;
            for(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<m;++i) c[i]=0;
            for(i=0;i<n;++i) c[x[y[i]]]++;
            for(i=1;i<m;++i) c[i]+=c[i-1];
            for(i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i];

            swap(x,y); p=1; x[sa[0]]=0;
            for(i=1;i<n;++i) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            if(p>=n) break; m=p;
        }
        int k=0; n--;
        for(i=0;i<=n;++i) rank[sa[i]]=i;
        for(i=0;i<n;++i){
            if(k) k--;
            j=sa[rank[i]-1];
            while(str[i+k]==str[j+k]) ++k;
            //height[rank[i]]=k;
        }
    }
    /*void initlcp(int n){
    	lg2[0]=-1;for(int i=1;i<N;++i) lg2[i]=(i&(i-1))?lg2[i-1]:lg2[i-1]+1;
        for(int i=1;i<=n;++i)
            rmq[0][i]=height[i];
        for(int k=1;k<=lg2[n];++k)
            for(int i=1;i+(1<<k)-1<=n;++i)
                rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<<(k-1))]);
    }
    int lcp(int a,int b){
        a=rank[a]; b=rank[b];
        if(a>b) swap(a,b); a+=1;
        int d=lg2[b-a+1];
        return min(rmq[d][a],rmq[d][b-(1<<d)+1]);
    }*/
}sa;
char s[M];
int B[M];
int main()
{
	cin>>s;
	int n =strlen(s);
	for(int i=0;i<n;i++)sa.str[i]=s[i]-'\0'+1;
	sa.gao(n,260);
	for(int i=1;i<=n;i++)printf("%d ",sa.sa[i]+1);
	puts("");
	return 0;
}

倍增

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e6+7;

struct SA{
    int sa[M],c[M],Rank[M],t1[M],t2[M];
    //rak[i]  下标i的后缀的排名
	//sa[i]    排名i (从0到n-1)的后缀的下标
	//待排序的字符串放在 s 数组中，从 s[0]到 s[n-1]，长度为 n，且最大值小于 m。 
	//约定除 s[n-1]外所有的 s[i]都大于 0, s[n-1]=0。函数结束后，结果放在 sa 数组中，从 sa[0]到 sa[n-1]。
    void Debug(int n,int m) 
	{
	    printf("*****************\n");
	    printf("下标"); for (int i = 0; i < n; i++) printf("%d ", i);     printf("\n");
	    printf("sa  "); for (int i = 0; i < n; i++) printf("%d ", sa[i]); printf("\n");
	    printf("c "); for (int i = 0; i < m; i++) printf("%d ", c[i]); printf("\n");
	    printf("x  "); for (int i = 0; i < n; i++) printf("%d ", t1[i]); printf("\n");
	    printf("y  "); for (int i = 0; i < n; i++) printf("%d ", t2[i]); printf("\n");
	}
	void gao(int* s,int n,int m)//字符集，字符集大小，字符集范围 
	{
        s[n]=0;
        int* x=t1,*y=t2;
        for(int i=0;i<m;i++) c[i]=0;//基数排序，数值i的桶里元素个数 
        for(int i=0;i<n;i++) c[x[i]=s[i]]++;
        for(int i=1;i<m;i++) c[i]+=c[i - 1] ;//基数排序，数值i的桶里元素的排名最大值 
        for(int i=n-1; i >= 0; i--) sa[--c[x[i]]]=i;
      //  Debug(n,m);
         //这里 x 数组保存的值相当于是 rank 值，下标i的排名(有重复)。下面的操作只是用 x 数组来比较字符的大小，所以没有必要求出当前真实的 rank 值
        for(int k=1;k<=n;k<<=1)
		{
            int p=0 ;//y数组保存的是，按第二关键字排序后的数组下标 
            for(int i=n-k;i<n;i++) y[p++]=i ;//这些位置无后k个，即第二关键字在前 
            for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;//利用上次基数排序的第一关键字当这次的第二关键字 
            for(int i=0;i<m;i++) c[i]=0;
            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];//基数排序 
    //        Debug(n,m);
            swap(x,y);p =1;x[sa[0]]=0;
            for(int i=1;i<n;i++)
                x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;
            if(p>=n)break ;
            m=p;
        }
        for(int i=0;i<n;i++)Rank[sa[i]]=i;
       // Debug(n,m);
    }
}suf;
char s[M];
int B[M];
int main()
{
	cin>>s;
	int n =strlen(s);
	for(int i=0;i<n;i++)B[i]=s[i]-'\0'+1;
	suf.gao(B,n,260);
	for(int i=0;i<n;i++)printf("%d ",suf.sa[i]+1);
	puts("");
	return 0;
}