JSOI2007 字符加密

题目链接：https://www.luogu.com.cn/problem/P4051

抽了点时间复习了一下后缀数组
这道题其实不难
将字符串拉环成链， 然后再求后缀数组即可
这样后缀排序出来，与原题所要求的顺序相符（可以自行推理）

$Code$

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2e5;
char str[MAXN + 10];
int rk[MAXN + 10], sa[MAXN + 10], id[MAXN + 10];namespace SA{
    void Rsort(int, int);void get_sa(int);
}
using namespace SA;int main(){
    
// freopen ("std.in", "r", stdin);
// freopen ("std.out", "w", stdout);scanf("%s", str + 1);int n = strlen(str + 1);for (register int i = n + 1; i <= n + n; ++i)	str[i] = str[i - n];get_sa(n + n);return 0;
}namespace SA{
    void Rsort(int n, int m){
    static int buck[MAXN + 10];for (register int i = 1; i <= m; ++i)	buck[i] = 0;for (register int i = 1; i <= n; ++i)	++buck[rk[i]];for (register int i = 1; i <= m; ++i)	buck[i] += buck[i - 1];for (register int i = n; i >= 1; --i)	sa[ buck[rk[id[i]]]-- ] = id[i];}void get_sa(int n){
    int m = 127, p = 0;for (register int i = 1; i <= n; ++i){
    rk[i] = (int)str[i];id[i] = i;}Rsort(n ,m);for (register int len = 1; p < n; m = p, len <<= 1){
    p = 0;for (register int i = 1; i <= len; ++i)	id[++p] = n - len + i;for (register int i = 1; i <= n; ++i)if (sa[i] > len)	id[++p] = sa[i] - len;Rsort(n, m);swap(rk, id);rk[sa[1]] = p = 1;for (register int i = 2; i <= n; ++i)rk[sa[i]] = (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + len] == id[sa[i - 1] + len])? p : ++p;}for (register int i = 1; i <= n; ++i)if (sa[i] <= n / 2)	printf("%c", str[sa[i] + n / 2 - 1]);}
}