\(令c_i=min_{1\leq i < j, t_j=t_i}\{j-i\} \)
\(B数组其实就是c_1 c_2 c_3 … c_n的后缀数组 \)
\(要注意若没有t_j=t_i，则c_i = n，同时c_{n+1} = n+1 \)
\(答案就是后缀数组的逆序 \)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<stdio.h> #include<iostream> #include<string.h> #define MAXN 100010 using namespace std; int n, sa[MAXN], rk[MAXN], oldrk[MAXN], id[MAXN], px[MAXN], cnt[MAXN], s[MAXN]; char str[MAXN]; void buildSA() { memset(cnt, 0, sizeof(cnt)); int m = n, *x = rk, *y = oldrk; for (int i = 1; i <= n; ++i) ++cnt[x[i] = s[i]]; for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1]; for (int i = n; i >= 1; --i) sa[cnt[x[i]]--] = i; for (int w = 1, p; w < n; w <<= 1) { p = 0; for (int i = n; i > n-w; --i) id[++p] = i; for (int i = 1; i <= n; ++i) { if (sa[i] > w) id[++p] = sa[i]-w; } memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; ++i) ++cnt[px[i] = x[id[i]]]; for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1]; for (int i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i]; swap(x, y); p = 0; for (int i = 1; i <= n; ++i) { x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+w] == y[sa[i-1]+w] ? p : ++p; } if (p >= n) break; m = p; } } int main() { while (scanf("%d", &n) != EOF) { scanf("%s", str+1); int pa = 0, pb = 0; for (int i = n; i >= 1; --i) { if (str[i] == 'a') { s[i] = !pa ? n : pa-i; pa = i; } else { s[i] = !pb ? n : pb-i; pb = i; } } n++; s[n] = n; buildSA(); for (int i = n-1; i >= 1; --i) printf("%d ", sa[i]); printf("\n"); } return 0; } |