# [BZOJ 1031][JSOI 2007] 字符加密Cipher【后缀数组】

• 2018-02-23
• 0
• 0

## Problem:

• JSOI07
• SOI07J
• OI07JS
• I07JSO
• 07JSOI
• 7JSOI0

• 07JSOI
• 7JSOI0
• I07JSO
• JSOI07
• OI07JS
• SOI07J

### Sample Input

```JSOI07
```

### Sample Output

```I0O7SJ
```

## Code: O(nlogn), n为环长度 [4616K, 712MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

char s[200005];
int n, SA[200005];

inline void buildSA(int m){
int *x = new int[200005], *y = new int[200005], *cnt = new int[200005];
for(register int i = 0; i < m; i++) cnt[i] = 0;
for(register int i = 0; i < n; i++) cnt[x[i] = s[i]]++;
for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
for(register int k = 1; k <= n; k <<= 1){
int p = 0;
for(register int i = n - k; i < n; i++) y[p++] = i;
for(register int i = 0; i < n; i++) if(SA[i] >= k) y[p++] = SA[i] - k;
for(register int i = 0; i < m; i++) cnt[i] = 0;
for(register int i = 0; i < n; i++) cnt[x[y[i]]]++;
for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
swap(x, y), p = 1, x[SA[0]] = 0;
for(register int i = 1; i < n; i++) x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? p - 1 : p++;
if(p == n) break;
m = p;
}
}

int main(){
fgets(s, 100005, stdin), n = strlen(s), s[n - 1] == '\n' ? n-- : 0;  // fgets() 会将 '\n' 读入, 需要删去
for(register int i = 0; i < n; i++) s[i + n] = s[i];  // 拆环成链
n <<= 1, s[n++] = 0, buildSA(128);
for(register int i = 1; i < n; i++)
if(SA[i] && SA[i] <= n - 1 >> 1) putchar(s[SA[i] - 1]);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai