【洛谷 P4051】 [JSOI2007]字符加密（后缀数组）

题目链接
两眼题。。
第一眼裸SA
第二眼要复制一倍再跑SA。
一遍过。。

#include <cstdio>
#include <cstring> 
#include <algorithm>
using namespace std;
const int MAXN = 1000010;
int sa[MAXN], x[MAXN], c[MAXN], y[MAXN], n, m = 122, q[MAXN], out[MAXN];
char s[MAXN];
int cmp(const int a, const int b){
    return x[a] < x[b];
}
int main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++i) s[i + n] = s[i];
    n <<= 1;
    for(int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
    for(int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for(int i = 1; i <= n; ++i)     sa[c[x[i]]--] = i;
    for(int k = 1; k <= n; k <<= 1){
       int num = 0;
       for(int i = n; i >= n - k + 1; --i) y[++num] = i;
       for(int i = 1; i <= n; ++i) if(sa[i] > k) y[++num] = sa[i] - k;
       for(int i = 1; i <= m; ++i) c[i] = 0;
       for(int i = 1; i <= n; ++i) ++c[x[i]];
       for(int i = 2; i <= m; ++i) c[i] += c[i - 1];
       for(int i = n; i; --i) sa[c[x[y[i]]]--] = y[i]; 
       memcpy(y, x, sizeof x);
       x[sa[1]] = 1; num = 1;
       for(int i = 2; i <= n; ++i)
          x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if(num == n) break;
        m = num;
    }
    n >>= 1;
    for(int i = 1; i <= n; ++i) q[i] = i;
    sort(q + 1, q + n + 1, cmp);
    for(int i = 1; i <= n; ++i)
       printf("%c", s[q[i] + n - 1]);
    return 0;
}

【洛谷 P4051】 [JSOI2007]字符加密（后缀数组）

原文：https://www.cnblogs.com/Qihoo360/p/10306537.html