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. 输出剩余的数据，即可完成 ```c++
   #include
   #include
   #include
   #include
   #include
   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=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=k) tp[p++] = SA[i] - k;
for (int i=0;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) break;
m = p;
}
}
void clear() {}
void init() {
//初始化
clear();
//输入
for (int i=0;i=0;i–) {
pos[n] = i;
a[n++] = ls[i];
}
a[n++] = 0;
build_SA();
for (int i=1;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=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;
}
```