从0开始的后缀数组为什么要在最后加$

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

const int Maxn = 1000000 + 10;
string str;
int n, m, len;
int sa[Maxn], rnk[Maxn], tp[Maxn], tax[Maxn];
// sa: 排名为 i 的后缀的位置
// rnk: 后缀 suffix[i] 的排名
// tp: 第二关键字排名为 i 的后缀的位置(基数排序用)
// tax: 元素 i 的出现次数(这里指的是排名)，注意排名的出现次数是 n 级别的
int cnt = 0;
void print() {
	printf("***************** %d \n", ++cnt);
	printf("     "); for (int i = 0; i < n; i++) printf("%d ", i);     printf("\n");
	printf("sa   "); for (int i = 0; i < n; i++) printf("%d ", sa[i]); printf("\n");
	printf("rnk  "); for (int i = 0; i < n; i++) printf("%d ", rnk[i]); printf("\n");
	printf("tp   "); for (int i = 0; i < n; i++) printf("%d ", tp[i]); printf("\n");
	// printf("*****************\n");
}

void quick_sort() {
	// print();
	for(int i = 0; i < m; ++i) tax[i] = 0;
	for(int i = 0; i < n; ++i) tax[rnk[i]]++;
	for(int i = 1; i < m; ++i) tax[i] += tax[i - 1];
	// tax 就是桶，做前缀和之后桶内数组的排名区间已知，只需要处理先后关系
	for(int i = n - 1; i >= 0; --i) sa[--tax[rnk[tp[i]]]] = tp[i];
	/* 在 quick_sort() 之前我们就已经将第二关键字按照大小关系排序了
	 * 从大到小枚举第二关键字，再用 rnk[i] 定位到第一关键字的大小
	 * tax[rnk[tp[i]]] 就表示当第一关键字相同时，第二关键字较大的这个后缀的排名是啥
	 */
	 // print();
}

void suffix_sort() {
	for(int i = 0; i < n; ++i) rnk[i] = str[i], tp[i] = i;
	quick_sort();
	for(int w = 1, p = 0; p + 1 < n; m = p + 1, w <<= 1) {
		p = 0;
		for(int i = n - w; i < n; ++i) tp[p++] = i;
		// 这些后缀的第二关键字设置最小
		for(int i = 0; i < n; ++i)
			if(sa[i] >= w) tp[p++] = sa[i] - w;
		// 比如第 i 位的第二关键字位置是 i + w，那么 sa[i] 自然就是 sa[i] - w 的第二关键字
		// 显然对于 j < w，j 是不可能成为第二关键字的
		// 而 sa 本来就是按照大小排序过的，所以只需要将 sa 数组复制给 tp
		quick_sort();
		swap(tp, rnk);
		rnk[sa[0]] = p = 0;
		for(int i = 1; i < n; ++i)
			rnk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
		// 本来应该 rnk[sa[i]] = i，但是相同的串应该是相同的排名
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("sample.in", "r", stdin);
	freopen("output.out", "w", stdout);
	ios::sync_with_stdio(false);
#endif
	cin >> str; //str = str + '$';
	n = str.length(); m = 0;
	for(int i = 0; i < n; ++i) m = max(m, (int)str[i]);
	++m;
	suffix_sort();
	for(int i = 0; i < n; ++i) cout << sa[i] + 1 << " ";
	return 0;
}