本文主要是介绍poj 3581 Sequence(后缀数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：对于第一段序列，因为第一个数最大所以最小的序列等于反串之后的字典序最小子串。用后缀数组可求。
之后在剩下的子串中，想分割出两个子串使得反转之后字典序最小，可以这样考虑:
先把剩下的字符串进行反转复制两次，样例中去掉第一段序列后剩下的子串为{2， 3， 4}，处理完为：
{4， 3 ， 2， 4 ，3， 2},可以发现{2， 4， 3}这个子串符合题目要求，而且{2}和{4. 3} 正好为{2, 3, 4}分割开的反串。
这个子串的首位可以用后缀数组处理出来。
/************************************************ Author: fisty* Created Time: 2015-08-22 17:23:23* File Name : N.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
//n*(logn)^2
#define MAX_N 200010
int N, k;
int sa[MAX_N * 2], rank[MAX_N], tmp[MAX_N+1];
int lcp[MAX_N];
int a[MAX_N * 2];
bool compare_sa(int i, int j){if(rank[i] != rank[j]) return rank[i] < rank[j];else{int ri = i + k <= N ? rank[i + k] : -1;int rj = j + k <= N ? rank[j + k] : -1;return ri < rj;}
}
int len(int *x){int l = 0;while(x[l++] != -1);return l-1;
}
void construct_sa(int S[]){//for(int i = 0;i < 5; i++){// Debug(S[i]);//}N = len(S);for(int i = 0;i <= N; i++){sa[i] = i;rank[i] = i < N ? S[i] : -1;}for(k = 1;k <= N; k *= 2){sort(sa, sa+N+1, compare_sa);tmp[sa[0]] = 0;for(int i = 1;i <= N; i++){tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);}for(int i = 0;i <= N; i++){rank[i] = tmp[i];}}
}
int n;
int rev[MAX_N * 2];void solve(){Memset(rev, -1);reverse_copy(a, a + n, rev);construct_sa(rev);int p1;for(int i = 0;i < n; i++){p1 = n - sa[i];// Debug(p1);if(p1 >= 1 && n - p1 >= 2) break; //分割的位置满足第一个串长度大于1并且后两个子串长度大于都1}//将p1之后的字符串反转两次再计算其后缀数组int m = n - p1;Memset(rev, -1);reverse_copy(a + p1,a + n, rev);reverse_copy(a + p1,a + n, rev + m);construct_sa(rev);//for(int i = 0;i < 2*m; i++){// Debug(rev[i]);//}//确定后两段的分割位置int p2;for(int i = 0;i <= 2 * m; i++){p2 = n - sa[i];if(p2 - p1 > 0 && n - p2 >= 1) break; //分割的位置满足大于第一个分割的位置并且第三个子串长度大于1}reverse(a, a + p1);reverse(a + p1, a + p2);reverse(a + p2, a + n);for(int i = 0;i < n; i++){printf("%d\n", a[i]);}
}
int main(){//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &n);for(int i = 0;i < n; i++){scanf("%d", &a[i]);}solve();return 0;
}
这篇关于poj 3581 Sequence(后缀数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
