题目链接：BZOJ1031
题目大意 给出一个字符串，将整个串循环位移生成的所有字符串排序，并以此输出所有串的最后一位。
分析 将串延长一倍，然后后缀数组，没了。 ps. 就当把后缀数组复习一遍吧。
上代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 10; int n; char ss[N << 1]; int sa[N << 1]; int rx[N << 1], ry[N << 1], rz[N << 1]; inline bool comp(int a, int l) { if (ry[sa[a]] == ry[sa[a - 1]]) if (ry[sa[a] + l] == ry[sa[a - 1] + l]) return true; return false; } void csort(int m) { memset(rz, 0, sizeof(rz)); for (int i = 1; i <= n; i++) rz[rx[ry[i]]]++; for (int i = 1; i <= m; i++) rz[i] += rz[i - 1]; for (int i = n; i >= 1; i--) sa[rz[rx[ry[i]]]--] = ry[i]; } void getSA(int m) { for (int i = 1; i <= n; i++) rx[i] = ss[i], ry[i] = i; csort(m); for (int p = 0, l = 1; l <= n; l <<= 1, p = 0) { for (int i = n - l + 1; i <= n; i++) ry[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] > l) ry[++p] = sa[i] - l; csort(m), swap(rx, ry); rx[sa[1]] = p = 1; for (int i = 2; i <= n; i++) rx[sa[i]] = comp(i, l) ? p : ++p; if (m = p, p == n) break; } } char ans[N]; int main() { scanf("%s", ss + 1); n = strlen(ss + 1); for (int i = 1; i <= n; i++) ss[i + n] = ss[i]; n <<= 1, getSA(200); for (int i = 1; i <= n; i++) if (sa[i] <= n / 2) printf("%c", ss[sa[i] + n / 2 - 1]); puts(""); return 0; }以上
