BZOJ 1031: [JSOI2007]字符加密Cipher

/* ???BZOJ 1031: [JSOI2007]字符加密Cipher ???把原串复制一遍 ???然后求一遍后缀数组即可*/#include <cstdio>#include <cstring>#define Max 1000008void read (int &now){ ???register char word = getchar (); ???for (now = 0; word < ‘0‘ || word > ‘9‘; word = getchar ()); ???for (; word >= ‘0‘ && word <= ‘9‘; now = now * 10 + word - ‘0‘);}inline void Swap (int *&a, int *&b){ ???int *now = a; ???a = b; ????b = now;} int sa[Max], rank[Max];int height[Max];char line[Max];int str_1[Max], str_2[Max];int N, M;void Get_Suffix (){ ???register int i; ???static int c[Max], *x = str_1, *y = str_2; ???for (i = 0; i < M; c[i ++] = 0); ???for (i = 0; i < N; c[x[i] = line[i]] ++, i ++); ???for (i = 1; i < M; c[i] += c[i - 1], i ++); ???for (i = N - 1; i >= 0; sa[-- c[x[i]]] = i --); ???register int pos; ???pos = 1; ???for (int j = 1; pos < N; j <<= 1, M = pos) ???{ ???????pos = 0; ???????for (i = N - j; i < N; y[pos ++] = i ++); ???????for (i = 0; i < N; i ++) ???????????if (sa[i] >= j) ???????????????y[pos ++] = sa[i] - j; ???????for (i = 0; i < M; c[i ++] = 0); ???????for (i = 0; i < N; c[x[y[i]]] ++, i ++); ???????for (i = 0; i < M; c[i] += c[i - 1], i ++); ???????for (i = N - 1; i >= 0; sa[-- c[x[y[i]]]] = y[i --]); ???????Swap (x, y); ???????pos = 1; ???????x[sa[0]] = 0; ???????for (i = 1; i < N; i ++) ???????????x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j] && sa[i - 1] + j < N && sa[i] + j < N) ? pos - 1 : pos ++; ???}}int main (int argc, char *argv[]){ ???scanf ("%s", line); ???N = strlen (line); ???M = 256; ??????for (int i = 0; i < N; ++ i) line[i + N] = line[i]; ????line[N << 1] = 0; ??????int P = N; N = 2 * N + 1; ???Get_Suffix (); N = P; ???for (int i = 0; i < N * 2 + 1; i ++) ???????if (sa[i] < N) printf ("%c", line[N + sa[i] - 1]); ???return 0;}