这是全部代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define R register
#define LL long long
const int inf = 0x3f3f3f3f;
const int N = 2e6 + 10;
inline int read() {
char a = getchar(); int x = 0,f = 1;
for(;a > '9' || a < '0';a = getchar()) if(a == '-') f = -1;
for(;a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
return x * f;
}
int n, m = 128;
char s[N];
int x[N], y[N], c[N], sa[N];
inline void qsort() {
for(R int i = 1; i <= m; i ++) c[i] = 0;
for(R int i = 1; i <= n; i ++) c[x[i]] ++;
for(R int i = 2; i <= m; i ++) c[i] += c[i - 1];
for(R int i = n; i >= 1; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
}
int main() {
freopen("a.in","r",stdin);
scanf("%s", s + 1); n = strlen(s + 1);
for(R int i = 1; i <= n; i ++) x[i] = s[i], y[i] = i;
qsort();
for(R int k = 1; k <= n; k = k << 1) {
int num = 0;
for(R int i = n - k + 1; i <= n; i ++) y[++ num] = i;
for(R int i = 1; i <= n; i ++)
if(sa[i] > k) y[++ num] = sa[i] - k;
qsort(); swap(x, y);
num = 1; x[sa[1]] = 1;
for(R int i = 2; i <= n; i ++)
if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num;
else x[sa[i]] = ++ num;
if(num == n) break;
m = num;
}
for(R int i = 1; i <= n; i ++) printf("%d ", sa[i]); putchar('\n');
return 0;
}
请问
for(R int i = n; i >= 1; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
和
for(R int i = n - k + 1; i <= n; i ++) y[++ num] = i;
for(R int i = 1; i <= n; i ++)
if(sa[i] > k) y[++ num] = sa[i] - k;
到底啥意思 ?