（突然发现自己不会写了）
by huayucaiji @ 2020-06-27 09:08:42
~~换个DC3试试~~
by 鏡音リン @ 2020-06-27 09:10:25
```cpp
int n,k,m,w[maxn],f[maxn][22],a[maxn],b[maxn],height[maxn],sa[maxn],t[maxn],rnk[maxn],c[maxn*20];
//sa表示排名为i的后缀的起始位置
//rnk表示起始为i的后缀排名第几
void bucket_sort(int v[]) {
fill(c,c+m+1,0);
for(int i=1;i<=n;i++) {
c[v[i]+1]++;
}
for(int i=1;i<=m;i++) {
c[i]+=c[i-1];
}
for(int i=1;i<=n;i++) {
t[++c[v[sa[i]]]]=sa[i];
}
for(int i=1;i<=n;i++) {
sa[i]=t[i];
}
}
void get_rnk(){
m=0;
for(int i=1;i<=n;i++) {
if(a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]]) {
m++;
}
rnk[sa[i]]=m;
}
}
void suffix_array() {
for(int i=1;i<=n;i++) {
a[i]=w[i];
b[i]=0;
sa[i]=i;
}
bucket_sort(a);
get_rnk();
for(int l=1;l<n;l<<=1) {
for(int i=1;i<=n;i++) {
a[i]=rnk[i];
if(i+l<=n) {
b[i]=rnk[i+l];
}
else {
b[i]=0;
}
}
bucket_sort(b);
bucket_sort(a);
get_rnk();
}
}
void get_height() {
int last=0;
//h[i]>=h[i-1]-1;
for(int i=1;i<=n;i++) {
if(last>0) {
last--;
}
if(rnk[i]==1) {
continue;
}
int p=i+last;
int q=sa[rnk[i]-1]+last;
while(p<=n&&q<=n&&w[p]==w[q]) {
last++;
p++;
q++;
}
height[rnk[i]]=last;
}
}
int query(int x,int y) {
int lg=log2(y-x+1);
return min(f[x][lg],f[y-(1<<lg)+1][lg]);
}
```
by huayucaiji @ 2020-06-27 09:10:31
这是我的倍增，~~DC3不会~~
by huayucaiji @ 2020-06-27 09:10:52
~~题解区有我写的DC3（疯狂推销）~~
by 鏡音リン @ 2020-06-27 09:12:36
@[wangjinbo](/user/228843) 清零换成memset，优化可以参考https://oi-wiki.org/string/sa/
by cbio @ 2020-06-27 09:54:37