这是一份能通过 luogu 和 loj 的评测但是无法通过 oirush 的倍增法代码。（正在找茬）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char st[N];
int sa[N],rk[N*2],lst[N*2],p;
bool cmp(int x,int y){return rk[x]!=rk[y]?rk[x]<rk[y]:rk[x+p]<rk[y+p];}
signed main()
{
	cin>>(st+1);int n=strlen(st+1);
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=st[i];
	for(p=1;p<n;p<<=1)
	{
		sort(sa+1,sa+n+1,cmp);
		memcpy(lst,rk,sizeof(rk));
		for(int i=1,cnt=0;i<=n;i++)
		{
			if(lst[sa[i]]==lst[sa[i-1]]&&lst[sa[i]+p]==lst[sa[i-1]+p])
				rk[sa[i]]=cnt;
			else rk[sa[i]]=++cnt;
		}
	}
	for(int i=1;i<=n;i++)cout<<sa[i]<<' ';
	return 0;	
}

F10 后缀数组(SA)

// Luogu P3809 【模板】后缀排序
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N=2000010;
char s[N];
int n,m;//n为后缀个数, m为桶的个数
int x[N],y[N],c[N],sa[N],rk[N],height[N];
//桶数组x[i],辅助数组y[i],计数数组c[i]
void get_sa(){
  int i,j,k;
  //按第一个字母排序
  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;i--)sa[c[x[i]]--]=i;
  for(k=1;k<=n;k<<=1){ //logn轮
    //按第二关键字排序
    memset(c,0,sizeof(c));
    for(i=1;i<=n;i++)y[i]=sa[i];
    for(i=1;i<=n;i++)c[x[y[i]+k]]++;
    for(i=1;i<=m;i++)c[i]+=c[i-1];
    for(i=n;i;i--)sa[c[x[y[i]+k]]--]=y[i];
    //按第一关键字排序
    memset(c,0,sizeof(c));
    for(i=1;i<=n;i++)y[i]=sa[i];
    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;i--)sa[c[x[y[i]]]--]=y[i];
    //把后缀放入桶数组
    for(i=1;i<=n;i++)y[i]=x[i];
    for(m=0,i=1;i<=n;i++)
      if(y[sa[i]]==y[sa[i-1]]&&
        y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=m;
      else x[sa[i]]=++m;
    if(m==n)break;//已排好    
  }  
}
void get_height(){
  int i,j,k;
  for(i=1;i<=n;i++)rk[sa[i]]=i;
  for(i=1,k=0;i<=n;i++){ //枚举后缀i
    if(rk[i]==1)continue;//第一名height为0
    if(k)k--;//上一个后缀的height值减1
    int j=sa[rk[i]-1];//找出后缀i的前邻后缀j
    while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
    height[rk[i]]=k;
  }
}
int main(){
  scanf("%s",s+1);
  n=strlen(s+1); m=122;
  get_sa();
  get_height();
  for(int i=1;i<=n;i++)printf("%d ",sa[i]);
  // puts("");
  // for(int i=1;i<=n;i++)printf("%d ",height[i]);
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;
char s[N];
int n, m;               // n 为字符串长度，m 为字符集大小（桶的个数）
int x[N], y[N], c[N];
// x[i]：存储当前排序第一关键字
// y[i]：存储当前第二关键字
// c[i]：计数排序的桶数组

int sa[N], rk[N], height[N]; 
// sa[i]：后缀数组，sa[i] 表示排名为 i 的后缀的起始位置
// rk[i]：名次数组，rk[i] 表示从位置 i 开始的后缀的排名（sa的逆数组）
// height[i]：高度数组，height[i] 表示排名为 i 的后缀与排名为 i - 1 的后缀的最长公共前缀长度

// 整体思想：通过倍增比较子串长度，逐步确定后缀的字典序排名
void get_sa() {
	memset(x, 0, sizeof(x));
	int i, j, k;   // 因为有很多 for，这仨经常用到，只定义一次减少 RE 风险 
	
	// 进行第一轮排序（类计数排序），按照每个后缀的第一个字符的字典序大小排序
    for (i = 1; i <= n; i++) {
		c[x[i] = s[i]] ++;     // 统计每个字符出现的次数，x[i] 初始化为 s[i] 的 ASCII 值
	}
    for (i = 1; i <= m; i++) {
		c[i] += c[i - 1];      // 计算前缀和
	}
    for (i = n; i >= 1; i--) {
		sa[c[x[i]]] = i;      // 根据前缀和确定每个后缀的排名，sa[i] 表示排名为 i 的后缀起始位置
		c[x[i]] --;
	}
    
    /* 倍增
     每次循环结束时，所有后缀字串按下标 1 到 2 * k 的字典序排序好 
	 比如 k = 2 时，原先长这样：
	 b
	 ab
	 aab
	 aaab
	 aaaab
	 aaaaab
	 就会这么排：
	 aaaab
	 aaaaab
	 aaab
	 aab
	 ab
	 b
	 也就是只管 1 到 2 * 2 的位置的字典序，长度大于 4 的位置就管不到了。
	  
	 那怎么实现呢？假设上一轮排序已经将 1 到 k 的下标字典序排好了
	 我们比较两个后缀 i 和 j 时，第一关键字是上一轮的 1 到 k 字典序 
	 第二关键字是第 1 + k 到 2 * k 的字典序
	 也就是说第一关键字是 x[i]，第二关键字是 x[i + k]，
	 
	 这个第二关键字应该怎么理解？
	 我们知道，每个后缀的 x[i] 代表着按 1 到 k 排该后缀 i 排第几位
	 而后缀的编号是不会变的，后缀 i 就是下标从 i 开始的后缀
	 也就是说 x[i + k] 代表着按 1 到 k 排后缀 i + k 排第几位，
	 但后缀 i + k 的前面 1 到 k 位，刚好就是后缀 i 的前面 1 + k 到 2 * k 位 
	  
	  所以这个倍增做法是正确的，是因为字串之间为后缀关系
	  （自己理解下） 
	*/ 
    for (k = 1; k <= n; k <<= 1) {     
        memset(c, 0, sizeof(c));       // 清空桶数组
        for (i = 1; i <= n; i ++) {
			y[i] = sa[i];      // 保存之前 1 到 k 的后缀数组
		}
		// 现在整个上一次的 sa 被当作第二关键字 y 排序 
        
        // 按 x[i + k] 排序
        for (i = 1; i <= n; i ++) {
			c[x[y[i] + k]] ++;  
			// 注意：y[i] + k 可能越界，但越界部分被视为相同（在计数排序中会自动排在前面）
			// 可以翻到文章内的代码下面，我有详细的模拟样例 
		}
        for (i = 1; i <= m; i ++) {
			c[i] += c[i - 1];    // 计算前缀和
		}
        for (i = n; i >= 1; i --) {
			sa[c[x[y[i] + k]]] = y[i];
			c[x[y[i] + k]] --;
		}
		// 现在第一关键字为 x[i + k]，第二关键字为 x[i]
		// 但我们想要第一关键字为 x[i]，第二关键字为 x[i + k]
        
        // 那么就在 x[i + k] 的基础上，以 x[i] 为第一关键字再排一遍 
        memset(c, 0, sizeof(c));     // 再次清空桶数组
        for (i = 1; i <= n; i ++) {
			y[i] = sa[i];  // 保存当前的后缀数组
		}
        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];
			c[x[y[i]]] --;
		}
		// 现在第一关键字为 x[i]，第二关键字为 x[i + k]
        
        // 重新计算排名，让 x[i] 代表按 1 到 2 * k 排该后缀 i 排第几位
        for (i = 1; i <= n; i ++) {
			y[i] = x[i];  // y 保存旧的排名
		}
        for (m = 0, i = 1; i <= n; i ++) {
            // 如果当前后缀和前一个后缀的第一关键字和第二关键字都相同，则排名相同
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) {
                x[sa[i]] = m;  // 排名不变
            }
            else {
            	m ++;
                x[sa[i]] = m;  // 反之排名增加
            }
        }
        
        // 如果所有后缀都已经有唯一排名，就结束
        if (m == n) {    // m == n 表示所有后缀都有不同的排名
			break;
		}
    }
}

/*
 构建高度数组（LCP 数组）
 height[i] 表示排名为 i 的后缀与字典序排名为 i - 1 的后缀的最长公共前缀长度（LCP） 
 使用了 height 数组的一个重要性质：height[rk[i]] >= height[rk[i - 1]] - 1
 
 证明： 
 已知当前后缀 rk[i] 的起始位置比 rk[i - 1] 后一位，假设：
 rk[i] = s，rk[i - 1] = c + s （c 是一个字符，s 是一个字符串）
 rk[i - 1] 和它排名前一位的字符串 ss 的 LCP 为 k，
 
 （1）height[rk[i]] = height[rk[i - 1]] - 1 的情况 
 假设 ss 的首字母开头也是 c， 
 那么 rk[i] 的排名前一位的字符串肯定是 ss 去掉开头的 c， 
 所以 rk[i] 和它排名前一位的字符串 ss - c 的 LCP 为 k - 1。
 height[rk[i]] = height[rk[i - 1]] - 1
 
 （2）height[rk[i]] > height[rk[i - 1]] - 1 的情况 
  假设 ss 的首字母开头不是 c，
  那么 height[rk[i - 1]] - 1 = -1，
  height[rk[i]] 无论是什么都大于 - 1。
  height[rk[i]] > height[rk[i - 1]] - 1
 */
void get_height() {
    int i, j, k;
    memset(height, 0, sizeof(height));
    
    // 构建名次数组 rk（sa 的逆数组）
    // rk[sa[i]] = i 表示后缀起始位置是 sa[i] 的排名为 i
    for (i = 1; i <= n; i ++) {
		rk[sa[i]] = i;
	}
    
    // 计算 height 数组
    for (i = 1, k = 0; i <= n; i ++) {  // 枚举每个后缀（按原字符串位置）
        if (rk[i] == 1) {
			continue;    // 排名第一的后缀没有 LCP，height 为 0
		}
        
        // 根据性质：height[rk[i]] >= height[rk[i - 1]] - 1
        if (k) {
			k--;  // 上一个后缀的 height 值减 1（因为当前后缀是上一个后缀去掉首字符）
		}
        
        int j = sa[rk[i] - 1];  // 找出排名在当前后缀前一位的后缀
        // 计算最长公共前缀
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) {
			k ++;
		}
        
        height[rk[i]] = k;  // 记录 height 值（rk[i] 是当前后缀的排名）
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	 
    cin >> s + 1;
    n = strlen(s + 1);
    m = 122;              // 字符集大小（ASCII 码最大为 122，即 'z'）
    
    get_sa();          // 构建后缀数组
    get_height();     // 构建高度数组
    
    // 输出后缀数组（按排名顺序输出每个后缀的起始位置）
    for (int i = 1; i <= n; i ++) {
		cout << sa[i] << " ";
	}
    cout << "\n";
    
    return 0;
}