Input:

aaaaa

Output:

5 4 3 2 1

错误输出：

5 3 4 1 2 

错误程序（但是能 AC）：

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

char s[N];
int sa[N], rk[N], tmp[N + 1];
int n, k;

bool comp_sa(int i, int j) {
	if (rk[i] != rk[j]) return rk[i] < rk[j];
	else {
		int ri = i + k <= n ? rk[i + k] : -1;
		int rj = j + k <= n ? rk[j + k] : -1;
		return ri < rj;
	}
}

void calc_sa() {
	for (int i = 0; i <= n; i++) {
		rk[i] = s[i];
		sa[i] = i;
	}
	
	for (k = 1; k < N; k <<= 1) {
		sort(sa, sa + n, comp_sa);
		tmp[sa[0]] = 0;
		for (int i = 0; i < n; i++) tmp[sa[i + 1]] = tmp[sa[i]] + (comp_sa(sa[i], sa[i + 1]) ? 1 : 0);
		for (int i = 0; i < n; i++) rk[i] = tmp[i];
	}
}

int main() {
	cin >> s;
	n = strlen(s);
	calc_sa();
	for (int i = 0; i < n; i++) cout << sa[i] + 1 << ' ';
	return 0;
}

错误原因：

没有将最后一个 $a$ 和 \0 的排名区分开。