用 SA 比较前后缀字典序，为什么要在正反串之间加神秘字符？

没有理解，写了一个不加神秘字符的，实际上可以通过啊？

#include <cstdio>
#include <cstring>
char s[1000050];
int n, m, z, L, R, a[1000050], d[1000050], r[2000050], o[2000050], k[1000050], c[1000050];
bool C(int x, int y, int w) { return o[x] == o[y] && o[x + w] == o[y + w]; }
int main()
{
    m = 127;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf(" %c", s + i);
    for (int i = 1; i <= n; ++i)
        s[(n << 1) - i + 1] = s[i];
    n <<= 1;
    for (int i = 1; i <= n; ++i)
        ++c[r[i] = s[i]];
    for (int i = 1; i <= m; ++i)
        c[i] += c[i - 1];
    for (int i = n; i; --i)
        a[c[r[i]]--] = i;
    for (int w = 1, p = 0; p < n; w <<= 1, m = p)
    {
        p = 0;
        for (int i = n; i > n - w; --i)
            d[++p] = i;
        for (int i = 1; i <= n; ++i)
            if (a[i] > w)
                d[++p] = a[i] - w;
        memset(c, 0, sizeof c);
        for (int i = 1; i <= n; ++i)
            ++c[k[i] = r[d[i]]];
        for (int i = 1; i <= m; ++i)
            c[i] += c[i - 1];
        for (int i = n; i; --i)
            a[c[k[i]]--] = d[i];
        memcpy(o, r, sizeof o);
        p = 0;
        for (int i = 1; i <= n; ++i)
            r[a[i]] = C(a[i], a[i - 1], w) ? p : ++p;
    }
    L = 1;
    R = n >>= 1;
    while (L <= R)
    {
        if (s[L] < s[R])
            putchar(s[L++]);
        else if (s[L] > s[R])
            putchar(s[R--]);
        else
            putchar(r[L] < r[(n << 1) - R + 1] ? s[L++] : s[R--]);
        if (!(++z % 80))
            puts("");
    }
    return 0;
}