手机版网站优化,网站推广公司经理职责,网红营销推广,大安市网站1031: [JSOI2007]字符加密Cipher Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 7882 Solved: 3425[Submit][Status][Discuss]Description 喜欢钻研问题的JS同学#xff0c;最近又迷上了对加密方法的思考。一天#xff0c;他突然想出了一种他认为是终极的加密办法#… 1031: [JSOI2007]字符加密Cipher Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 7882 Solved: 3425[Submit][Status][Discuss] Description 喜欢钻研问题的JS同学最近又迷上了对加密方法的思考。一天他突然想出了一种他认为是终极的加密办法 把需要加密的信息排成一圈显然它们有很多种不同的读法。例如下图可以读作 JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J读出最后一列字符I0O7SJ就是加密后的字符串其实这个加密手段实在很容易破解鉴于这是 突然想出来的那就^^。但是如果想加密的字符串实在太长你能写一个程序完成这个任务吗 Input 输入文件包含一行欲加密的字符串。注意字符串的内容不一定是字母、数字也可以是符号等。 Output 输出一行为加密后的字符串。 Sample Input JSOI07 Sample Output I0O7SJ HINT 对于100%的数据字符串的长度不超过100000。 Source 后缀数组裸题。。 1 #include iostream2 #include cstdio3 #include cstring4 #include cstdlib5 #include algorithm6 #include queue7 #include vector8 #include cmath 9 #define min(a, b) ((a) (b) ? (a) : (b))
10 #define max(a, b) ((a) (b) ? (a) : (b))
11 #define abs(a) ((a) 0 ? (-1 * (a)) : (a))
12 template class T
13 inline void swap(T a, T b)
14 {
15 T tmp a;a b;b tmp;
16 }
17 inline void read(int x)
18 {
19 x 0;char ch getchar(), c ch;
20 while(ch 0 || ch 9) c ch, ch getchar();
21 while(ch 9 ch 0) x x * 10 ch - 0, ch getchar();
22 if(c -) x -x;
23 }
24 const int INF 0x3f3f3f3f;
25 const int MAXN 1000000 10;
26 char s[MAXN];
27 int sa[MAXN], tmp[MAXN], tmp2[MAXN], c[MAXN], n, m;
28 void build(char *s, int *sa, int n, int m)
29 {
30 int i, *x tmp, *y tmp2;
31 for(i 0;i m; i) c[i] 0;
32 for(i 0;i n; i) c[x[i] s[i]];
33 for(i 1;i m; i) c[i] c[i - 1];
34 for(i n - 1;i 0;-- i) sa[--c[x[i]]] i;
35 for(int k 1;k n;k 1)
36 {
37 int p 0;
38 for(i n - k; i n; i) y[p] i;
39 for(i 0; i n; i) if(sa[i] k) y[p] sa[i] - k;
40 for(i 0; i m; i) c[i] 0;
41 for(i 0; i n; i) c[x[y[i]]];
42 for(i 0; i m; i) c[i] c[i - 1];
43 for(i n - 1; i 0; i --) sa[-- c[x[y[i]]]] y[i];
44 swap(x, y);
45 p 1; x[sa[0]] 0;
46 for(i 1; i n; i)
47 x[sa[i]] y[sa[i - 1]] y[sa[i]] y[sa[i - 1] k] y[sa[i] k] ? p - 1 : p ;
48 if(p n) break;
49 m p;
50 }
51 }
52 int main()
53 {
54 scanf(%s, s);
55 n strlen(s);
56 for(register int i 0;i n; i) s[n i] s[i], m max(m, s[i] 1);
57 build(s, sa, n 1, m);
58 for(int i 0;i (n 1); i)
59 if(sa[i] n) printf(%c, s[sa[i] n - 1]);
60 return 0;
61 } BZOJ1031 转载于:https://www.cnblogs.com/huibixiaoxing/p/8328199.html
