poj 3581(后缀数组)

poj 3581

  1. 因为第一个数比后面的大,所以将原串翻转后找出排第$i$位的后缀输出,符合$SA[i]>=2$的最小$i$(后缀数组中的排列是字典序)
  2. 之后将之前已经处理的数据删掉,然后题目变为将剩下的数据分为两份翻转后字典序最小,那么我们设$S$为这个序列,$S_1, S_2, …, S_k, S_{k+1},…S_n$,其中$k$是分割点,处理后变为$S_k, S_{k-1}, …, S_1, S_n, S_{n-1},…,S_{k+1}$,我们发现这个序列是$S_n, S_{n-1}, …, S_1, S_n, S_{n-1},…,S_{1}$的子串,那么我们将翻转后的数列复制一份放在后面,然后找出排第$i$位的后缀输出,符合$SA[i]>=1, SA[i]∈第一部分$的最小$i$输出。(后缀数组中的排列是字典序,设法构造一个串,使得欲求串的字典序能够求出)
  3. 输出剩余的数据,即可完成
    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
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define ms(i, j) memeset(i, j, sizeof i)
    const int MAXN = 200000 + 5;
    int N, n, m, a[MAXN*2], SA[MAXN*2], tp[MAXN*2], tax[MAXN*2], rk[MAXN*2], pos[MAXN*2];
    int siz, inp[MAXN], ls[MAXN], sub_a[MAXN];
    bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];}
    void build_SA() {
    for (int i=0;i<m;i++) tax[i] = 0;
    for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
    for (int i=1;i<m;i++) tax[i] += tax[i-1];
    for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;
    int p;
    for (int k=1;k<=n;k*=2) {
    p = 0;
    for (int i=n-k;i<n;i++) tp[p++] = i;
    for (int i=0;i<=n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
    for (int i=0;i<m;i++) tax[i] = 0;
    for (int i=0;i<n;i++) tax[rk[tp[i]]]++;
    for (int i=1;i<m;i++) tax[i] += tax[i-1];
    for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];
    swap(tp, rk), p = 0, rk[SA[0]] = 0;
    for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
    if (++p>=n) break;
    m = p;
    }
    }
    void clear() {}
    void init() {
    //初始化
    clear();
    //输入
    for (int i=0;i<N;i++) {
    scanf("%d", &inp[i]); sub_a[i] = inp[i];
    }
    //离散化
    sort(sub_a, sub_a+N);
    siz = unique(sub_a, sub_a+N)-sub_a;
    for (int i=0;i<N;i++) {
    ls[i] = lower_bound(sub_a, sub_a+siz, inp[i]) - sub_a + 1;
    }
    }
    void solve() {
    int las = 0;
    //first
    n = 0, m = siz + 1;
    for (int i=N-1;i>=0;i--) {
    pos[n] = i;
    a[n++] = ls[i];
    }
    a[n++] = 0;
    build_SA();
    for (int i=1;i<n;i++) {
    if (SA[i]>=2) {
    las = pos[SA[i]];
    for (int j=las;j>=0;j--) printf("%d\n", inp[j]);
    break;
    }
    }
    //sec
    n = 0, m = siz + 1;
    int mid = 0, las2 = 0;
    for (int i=N-1;i>las;i--) {
    pos[n] = i;
    a[n++] = ls[i];
    }
    mid = n;
    for (int i=N-1;i>las;i--) {
    pos[n] = i;
    a[n++] = ls[i];
    }
    a[n++] = 0;
    build_SA();
    for (int i=1;i<n;i++) {
    if (SA[i]<mid&&SA[i]>=1) {
    las2 = pos[SA[i]];
    for (int j=las2;j>las;j--) printf("%d\n", inp[j]);
    break;
    }
    }
    //third
    for (int j=N-1;j>las2;j--) printf("%d\n", inp[j]);
    }
    int main() {
    scanf("%d", &N); init(), solve();
    return 0;
    }
------ 本文结束 ------