后缀数组（SA）做题记录

SA 真的是个好东西，好呀好东西。

基础定义：

$sa$ 数组：后缀排序后排名为 $i$ 的后缀的起始位置下标。

$rk$ 数组：起始下标为 $i$ 的后缀的排名。

$height$ 数组：后缀排序后排名为 $i$ 和 $i-1$ 的最长公共前缀长度（Lcp）

模板：（小bug：在SA代码

char ch[N];
struct Suffix_Array
{
    ll m=200,X[N],Y[N],c[N],num[N],sa[N],height[N],rk[N],lg[N],st[N][23];
    void Sa()
    {
        for(int i=1;i<=n;i++)X[i]=ch[i],c[X[i]]++;
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[X[i]]--]=i;
        for(int k=1,p=0;k<=n;k=k<<1,p=0)
        {
            for(int i=n-k+1;i<=n;i++)Y[++p]=i;
            for(int i=1;i<=n;i++)if(sa[i]>k)Y[++p]=sa[i]-k;
            for(int i=1;i<=m;i++)c[i]=0;
            for(int i=1;i<=n;i++)c[X[i]]++;
            for(int i=2;i<=m;i++)c[i]+=c[i-1];
            for(int i=n;i>=1;i--)sa[c[X[Y[i]]]--]=Y[i],Y[i]=0;
            swap(X,Y);p=1;X[sa[1]]=1;
            for(int i=2;i<=n;i++)
            {
                if(Y[sa[i]]==Y[sa[i-1]]&&Y[sa[i]+k]==Y[sa[i-1]+k])X[sa[i]]=p;
                else X[sa[i]]=++p;
            }
            if(p==n)return;m=p;
        }
    }
    void Height()
    {
        ll k=0;
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1;i<=n;i++)
        {
            if(rk[i]==1)continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<=n&&j+k<=n&&ch[i+k]==ch[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void St()
    {
        for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++)st[i][0]=height[i];
        for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    }
    int Lcp(int l,int r) //原数组中 l,r的lcp长度 
    {
        if((l=rk[l])>(r=rk[r]))swap(l,r); //若是直接在后缀数组sa[i]上求就删除 
        int d=lg[r-l++];
        return min(st[l][d],st[r-(1<<d)+1][d]); 
    }
}SA;

题目：

1.P3809 【模板】后缀排序

板子

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int N=1e6+3;
 6 int n,m=200,X[N],Y[N],c[N],sa[N],height[N],rk[N];
 7 char ch[N];
 8 void Sa()
 9 {
10     for(int i=1;i<=n;i++)X[i]=ch[i],c[X[i]]++;
11     for(int i=2;i<=m;i++)c[i]+=c[i-1];
12     for(int i=n;i>=1;i--)sa[c[X[i]]--]=i;
13     for(int k=1,p=0;k<=n;k=k<<1,p=0)
14     {
15         for(int i=n-k+1;i<=n;i++)Y[++p]=i;
16         for(int i=1;i<=n;i++)if(sa[i]>k)Y[++p]=sa[i]-k;
17         for(int i=1;i<=m;i++)c[i]=0;
18         for(int i=1;i<=n;i++)c[X[i]]++;
19         for(int i=2;i<=m;i++)c[i]+=c[i-1];
20         for(int i=n;i>=1;i--)sa[c[X[Y[i]]]--]=Y[i],Y[i]=0;
21         swap(X,Y);p=1;X[sa[1]]=1;
22         for(int i=2;i<=n;i++)
23         {
24             if(Y[sa[i]]==Y[sa[i-1]]&&Y[sa[i]+k]==Y[sa[i-1]+k])X[sa[i]]=p;
25             else X[sa[i]]=++p;
26         }
27         if(p==n)return;m=p;
28     }
29 }
30 void Height()
31 {
32     int k=0;
33     for(int i=1;i<=n;i++)rk[sa[i]]=i;
34     for(int i=1;i<=n;i++)
35     {
36         if(rk[i]==1)continue;
37         if(k)k--;
38         int j=sa[rk[i]-1];
39         while(i+k<=n&&j+k<=n&&ch[i+k]==ch[j+k])k++;
40         height[rk[i]]=k;
41     }
42 }
43 int main()
44 {
45     cin>>(ch+1);n=strlen(ch+1);
46     Sa();Height();
47     for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
48     return 0; 
49 }