[luoguP4051/JSOI2007] 字符加密

题意

给定字符串 \(s\)，输出将 \(s\) 的所有循环同构的字符串排序后，每个字符串的末尾的字符。

sol

因为要对循环同构的字符串排序，因此我们可以将 \(s\) 复制一遍，拼在后面，计算 \(sa\)，满足 \(sa_i \le n\) 的所有元素的相对位置即为排序后字符串的相对位置，输出即可
\(sa\) 的计算详见[luoguP3809]后缀排序

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 200005;

char s[N];
int n;
int sa[N], rk[N], oldrk[N], cnt[N], scd[N];

void get_sa(){
    for (int i = 1; i <= n; i ++ ) cnt[rk[i] = s[i]] ++ ;
    for (int i = 1; i <= 128; i ++ ) cnt[i] += cnt[i - 1];
    for (int i = n; i; i -- ) sa[cnt[rk[i]] -- ] = i;

    for (int w = 1, m = 128, p = 0; ; m = p, p = 0, w <<= 1){
        for (int i = n - w + 1; i <= n; i ++ ) scd[ ++ p] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > w) scd[ ++ p] = sa[i] - w;
        
        memset(cnt, 0, m + 1 << 2);
        memcpy(oldrk, rk, n + 1 << 2);

        for (int i = 1; i <= n; i ++ ) cnt[rk[i]] ++ ;
        for (int i = 1; i <= m; i ++ ) cnt[i] += cnt[i - 1];
        for (int i = n; i; i -- ) sa[cnt[rk[scd[i]]] -- ] = scd[i];
        
        p = 0;
        for (int i = 1; i <= n; i ++ ) rk[sa[i]] = (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ? p : ++ p;

        if (p >= n) return ;
    }
}

int main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i ++ ) s[i + n] = s[i];
    n <<= 1;

    get_sa();

    for (int i = 1; i <= n; i ++ ) 
        if (sa[i] <= (n >> 1)) printf("%c", s[sa[i] + (n >> 1) - 1]);

    return 0;
}