BZOJ1031 [JSOI2007]字符加密Cipher

浏览数：30 / 时间：2015年06月09日

把字符串倍长复制了。。。直接后缀数组求出rank就好了QAQ

 1 /**************************************************************
 2     Problem: 1031
 3     User: rausen
 4     Language: C++
 5     Result: Accepted
 6     Time:1252 ms
 7     Memory:4908 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13   
14 using namespace std;
15 const int N = 2e5 + 5;
16   
17 char s[N];
18 int l, sa[N], rank[N];
19 int x[N], y[N], sum[N];
20   
21 inline void Sort(int *a, int *b, int *c, int n, int m) {
22     static int i;
23     for (i = 0; i <= m; ++i) sum[i] = 0;
24     for (i = 0; i < n; ++i) ++sum[c[a[i]]];
25     for (i = 1; i <= m; ++i) sum[i] += sum[i - 1];
26     for (i = n - 1; ~i; --i)
27         b[--sum[c[a[i]]]] = a[i];
28 }
29   
30 void make_sa(char *s) {
31     int i, j;
32     for (i = 0; i < l; ++i) x[i] = s[i], rank[i] = i;
33     Sort(rank, sa, x, l, 256);
34     rank[sa[0]] = 1;
35     for (i = 1; i < l; ++i)
36         rank[sa[i]] = rank[sa[i - 1]] + (x[sa[i]] != x[sa[i - 1]]);
37     for (i = 1; i <= l; i <<= 1) {
38         for (j = 0; j < l; ++j)
39             x[j] = rank[j], y[j] = j + i < l ? rank[j + i] : 0, sa[j] = j;
40         Sort(sa, rank, y, l, l), Sort(rank, sa, x, l, l);
41         rank[sa[0]] = 1;
42         for (j = 1; j < l; ++j)
43             rank[sa[j]] = rank[sa[j - 1]] + (x[sa[j]] != x[sa[j - 1]] || y[sa[j]] != y[sa[j - 1]]);
44         if (rank[sa[l - 1]] == l) return;
45     }
46 }
47   
48 int main() {
49     int i;
50     gets(s), l = strlen(s);
51     for (i = l; i < l << 1; ++i) s[i] = s[i - l];
52     l <<= 1;
53     make_sa(s);
54     for (i = 0; i < l; ++i)
55         if (sa[i] < l / 2) putchar(s[sa[i] + l / 2 - 1]);
56     putchar(‘\n‘);
57     return 0;
58 }