uoj#35. 接尾辞ソート接尾辞配列
uoj#35. 接尾辞ソート裸の接尾辞配列・・・2回叩いて・・・QQQがlrjコードとあるAC神を参考にして書いたコードを忘れないように・・・
その神妙さに注釈をつけた
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=200005;
int n;
int sa[N],c[N],t1[N],t2[N];
int rank[N],height[N];
char s[N];
void buildsa(int m){
int i,*x=t1,*y=t2;
for(i=1;i<=m;i++) c[i]=0;
for(i=1;i<=n;i++) c[x[i]=s[i]]++;
for(i=1;i<=m;i++) c[i]+=c[i-1];
for(i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
for(i=n-k+1;i<=n;i++) y[++p]=i;
for(i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
for(i=1;i<=m;i++) c[i]=0;
for(i=1;i<=n;i++) c[x[y[i]]]++;
for(i=1;i<=m;i++) c[i]+=c[i-1];
for(i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=1;p=1;
for(i=2;i<=n;i++)
x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p;
if(p>=n) break;
m=p;
}
}
void getheight() {
int i,j,k=0;
for (i=1;i<=n;i++) rank[sa[i]]=i;
for (i=1;i<=n;i++) {
if (k) k--;
j=sa[rank[i]-1];
while (s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%s",s+1);n=strlen(s+1);
buildsa(128);
for(int i=1;i<=n;i++) printf("%d ",sa[i]);puts("");
getheight();
for(int i=2;i<=n;i++) printf("%d ",height[i]);puts("");
return 0;
}
その神妙さに注釈をつけた
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=200011;
char s[maxn];
int c[maxn],t1[maxn],t2[maxn],sa[maxn],rank[maxn],height[maxn],f[maxn][20];
int i,j,k,m,n;
// , s[1..n]
//sa[i] i s
//rank[i] i s
//height[i] i-1 i
void buildsa(int m,int *sa,char *s) {
int i,*x=t1,*y=t2;
for (i=1;i<=m;i++) c[i]=0;
for (i=1;i<=n;i++) c[x[i]=s[i]]++;// ， x[i]
for (i=1;i<=m;i++) c[i]+=c[i-1];//
for (i=n;i>=1;i--) sa[c[x[i]]--]=i;// 2^0
for (k=1;k<=n;k<<=1) {
// 2^k
int p=0;
//
for (i=n-k+1;i<=n;i++) y[++p]=i;//
for (i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k;//sa[i] sa[i] ， k ， ；
// k 。
//
for (i=1;i<=m;i++) c[i]=0;//
for (i=1;i<=n;i++) c[x[y[i]]]++;//
for (i=1;i<=m;i++) c[i]+=c[i-1];// |
for (i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];// sa
swap(x,y);//y rank
p=1;x[sa[1]]=1;
for (i=2;i<=n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p:++p;
if (p>=n) break;
m=p;
}
}
void getheight(char *s,int *sa,int *rank,int *height) {
int i,j,k=0;
for (i=1;i<=n;i++) rank[sa[i]]=i;// sa rank
for (i=1;i<=n;i++) {
if (k) k--;
j=sa[rank[i]-1];// height[rank[i]]>=height[rank[i-1]]-1 height
while (s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}
void initrmq(int f[maxn][20],int *height) {
int i,j;
for (i=1;i<=n;i++) f[i][0]=height[i];
for (j=1;1<<j<=n;j++)
for (i=1;i<=n-(1<<j)+1;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<j>>1)][j-1]);
}
int getrmq(int f[maxn][20],int i,int j) {
if (!i || !j) return 0;
if (i>j) swap(i,j);
int s=i+1,t=j,k;
for (k=0;(1<<k)<=t-s+1;k++);
k--;
return min(f[s][k],f[t-(1<<k)+1][k]);
}
int main() {
freopen("in.txt","r",stdin);
freopen("right.txt","w",stdout);
scanf("%s",s+1);n=strlen(s+1);
buildsa(128,sa,s);
getheight(s,sa,rank,height);
for (i=1;i<=n;i++) printf("%d ",sa[i]);
puts("");
for (i=2;i<=n;i++) printf("%d ",height[i]);
puts("");
return 0;
}