题目链接：【模板】后缀排序
学习链接： 后缀数组 最详细讲解 [知识点]后缀数组
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 1000010; int n, m; int y[N], x[N], c[N], rk[N], sa[N]; char s[N]; void get_sa() { for(int i = 0; i < n; i++) ++c[x[i] = s[i]]; for(int i = 1; i <= m; i++) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i; for(int k = 1; k <= n; k <<= 1) { int num = 0; for(int i = n - k; i < n; i++) y[num++] = i; for(int i = 0; i < n; i++) if(sa[i] >= k) y[num++] = sa[i] - k; for(int i = 0; i < m; i++) c[i] = 0; for(int i = 0; i < n; i++) c[x[y[i]]]++; for(int i = 0; i < m; i++) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x, y); num = 1; x[sa[0]] = 0; for(int i = 1; i < n; i++) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? num - 1 : num++; if(num >= n) break; m = num; } } int main() { scanf("%s", s); n = strlen(s); m = 'z'; get_sa(); for(int i = 0; i < n; i++) { printf("%d", sa[i] + 1); if(i == n - 1) printf("\n"); else printf(" "); } return 0; }