后缀数组（bzoj 1031: [JSOI2007]字符加密Cipher）

后缀数组主要功能：

长度为n的字符串总共有n个后缀，求这n个后缀的字典序

实现方法：倍增+基数排序，过程就是下面那张表

求log(n)次rank数组，每次的rank数组都可以通过上次的rank数组得出

最后的rank就是答案，过程看起来简单，但代码实现挺难得！

Rank[]：rank[i]=p表示下标为i开头的字符串排第p个

Sa[]：Sa[i]=p表示排第i个的字符串是下标为p开头的字符串

cot[]：辅助数组，cot[i]=p表示当前rank数组中值小于等于i的数的个数

例如rank[]：{1,2,4,1,1,1,2,3}，那么cot[1]==4，cor[2]==6，cot[3]==7，cot[4]==8

（或初始字符串中ASCLL码<=i的字符个数）

Temp[]：Temp[i]=p意思就是第二个数（图里y数组）中第i的小的是下标p上的数

参考博文：

http://www.cnblogs.com/shanchuan04/p/5324009.html

http://blog.csdn.net/yxuanwkeith/article/details/50636898

http://blog.csdn.net/qq_34731703/article/details/52934284

代码中有注释

1031: [JSOI2007]字符加密Cipher

Time Limit: 10 Sec   Memory Limit: 162 MB Submit: 7202   Solved: 3120 [ 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

题解：裸的后缀数组，因为是个环不是个后缀所以要将字符串复制一遍接在后面

然后就是模板

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char str[200100]; int a[200100], Rank[200100], Temp[200100], cot[200100], Sa[200100]; int main(void) { int n, i, m, p, k; while(scanf("%s", str+1)!=EOF) { n = strlen(str+1); for(i=1;i<=n;i++) { a[i] = a[i+n] = str[i]; str[i+n] = str[i]; } n *= 2, m = 128; memset(cot, 0, sizeof(cot)); for(i=1;i<=n;i++) { Rank[i] = a[i]; cot[a[i]]++; } for(i=1;i<=m;i++) cot[i] += cot[i-1]; // cot[i]表示ASCLL码小于等于i的字符个数 for(i=n;i>=1;i--) Sa[cot[a[i]]--] = i; /* puts(str+1); for(i=1;i<=n;i++) printf("%d ", Sa[i]); // 第一次排序，输入ABAAB，输出结果为： printf("\n"); // ABAABABAAB for(i=1;i<=n;i++) // 1 3 4 6 8 9 2 5 7 10 printf("%d ", Rank[i]); // 97 98 97 97 98 97 98 97 97 98 printf("\n"); */ for(k=1;k<=n;k*=2) { p = 0; for(i=n-k+1;i<=n;i++) //下标在[n+1, n+k]范围内的字符是空字符，所以字典序肯定是最小的 Temp[++p] = i; for(i=1;i<=n;i++) //前k个字符因为不参与排序，后面所有字符自动向前面移动k位（下标-k） { if(Sa[i]>k) Temp[++p] = Sa[i]-k; } /* printf("k=%d\nTemp: ", k); for(i=1;i<=n;i++) // 当k=1时，输出结果为： printf("%d ", Temp[i]); // 10 2 3 5 7 8 1 4 6 9 printf("\n"); */ memset(cot, 0, sizeof(cot)); for(i=1;i<=n;i++) /*这个时候，可以把rank当成新的a数组，之前的数组已经毫无意义*/ cot[Rank[i]]++; for(i=1;i<=m;i++) cot[i] += cot[i-1]; for(i=n;i>=1;i--) Sa[cot[Rank[Temp[i]]]--] = Temp[i]; /* Temp[i]=p意思就是第二个数（图里y数组）中第i的大的是下标p上的数*/ swap(Rank, Temp); p = 1; Rank[Sa[1]] = 1; //求出当前的rank数组，在这里之前的rank数组就已经毫无意义了 for(i=2;i<=n;i++) { if(Temp[Sa[i-1]]==Temp[Sa[i]] && Temp[Sa[i-1]+k]==Temp[Sa[i]+k]) Rank[Sa[i]] = p; else Rank[Sa[i]] = ++p; } m = p; /* printf("Rank: "); for(i=1;i<=n;i++) // 当k=1时，输出结果为： printf("%d ", Rank[i]); // 2 4 1 2 4 2 4 1 2 3 printf("\n"); */ } n /= 2; for(i=1;i<=2*n;i++) { if(Sa[i]>n) continue; printf("%c", str[Sa[i]+n-1]); } printf("\n"); } }