看了求后缀数组的倍增法之后很快就理解了, 但是自己写的倍增法用 map 排序还是超时了. 然后看了两天别人写的模板, 题目是通过了, 但感觉代码还是半懂半背的. 以后多熟悉熟悉吧;
- #include "bits/stdc++.h"
- using namespace std;
- const int MAXN = 1e6 + 5;
- char s[MAXN];
- int sa[MAXN], rk[MAXN], height[MAXN];
- void getSa(char* s, int* sa, int n, int m) {
- int* x = (int*)calloc(MAXN, sizeof(int));
- int* y = (int*)calloc(MAXN, sizeof(int));
- int* cnt = (int*)calloc(MAXN, sizeof(int));
- for (int i = 1; i <= n; i++) {
- cnt[x[i] = s[i]]++;
- }
- for (int i = 2; i <= m; i++) {
- cnt[i] += cnt[i - 1];
- }
- for (int i = n; i; i--) {
- sa[cnt[x[i]]--] = i;
- }
- for (int j = 1; j <n; j <<= 1) {
- int num = 0;
- for (int i = n - j + 1; i <= n; i++) {
- y[++num] = i;
- }
- for (int i = 1; i <= n; i++) {
- if (sa[i]> j) {
- y[++num] = sa[i] - j;
- }
- }
- for (int i = 1; i <= m; i++) {
- cnt[i] = 0;
- }
- for (int i = 1; i <= n; i++) {
- cnt[x[i]]++;
- }
- for (int i = 2; i <= m; i++) {
- cnt[i] += cnt[i - 1];
- }
- for (int i = n; i; i--) {
- sa[cnt[x[y[i]]]--] = y[i];
- }
- swap(x, y);
- x[sa[1]] = num = 1;
- for (int i = 2; i <= n; i++) {
- if (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + j] != y[sa[i - 1] + j]) {
- x[sa[i]] = ++num;
- } else {
- x[sa[i]] = num;
- }
- }
- if (num>= n) {
- break;
- }
- m = num;
- }
- free(x);
- free(y);
- free(cnt);
- }
- void getHeight(char* s, int* sa, int* rk, int* height, int n) {
- for (int i = 1; i <= n; i++) {
- rk[sa[i]] = i;
- }
- int k = 0;
- for (int i = 1; i <= n; i++) {
- k = k != 0 ? k - 1 : k;
- int j = sa[rk[i] - 1];
- while (s[i + k] == s[j + k]) {
- k++;
- }
- height[rk[i]] = k;
- }
- }
- int main() {
- gets(s + 1);
- int len = strlen(s + 1);
- getSa(s, sa, len, 130);
- // getHeight(s, sa, rk, height, len);
- for (int i = 1; i < len; i++) {
- printf("%d", sa[i]);
- }
- printf("%d\n", sa[len]);
- /*
- for (int i = 1; i < len; i++) {
- printf("%d", rk[i]);
- }
- printf("%d\n", rk[len]);
- for (int i = 1; i < len; i++) {
- printf("%d", height[i]);
- }
- printf("%d\n", height[len]);
- */
- return 0;
- }
附带 rank 数组和 height 数组, 本题不需要.
来源: http://www.bubuko.com/infodetail-2933987.html