SA 真的是个好东西,好呀好东西。
基础定义:
$sa$ 数组:后缀排序后排名为 $i$ 的后缀的起始位置下标。
$rk$ 数组:起始下标为 $i$ 的后缀的排名。
$height$ 数组:后缀排序后排名为 $i$ 和 $i-1$ 的最长公共前缀长度(Lcp)
模板:(小bug:在SA代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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;View Code
题目:
板子
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 }View Code
标签:ch,后缀,int,数组,--,SA,sa From: https://www.cnblogs.com/Hanghang007/p/17599145.html