后缀数组模板+POJ3581
后缀数组指的是将某个字符串的所有后缀按字典序排序后得到的数组，基本概念可参考后缀数组。
下面为后缀数组的模板
import java.util.Scanner;

public class Main {

	static int[] sa;//后缀数组suffix array
	static int[] cnt;//计数数组
	static int[] x;
	static int[] y;
	static String str;
	static int length;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		//输入一个字符串
		str = in.next();
		sa = new int[500];
		cnt = new int[500];
		x = new int[500];
		y = new int[500];
		sa();
		for(int i = 0;i < length;i++) {
			System.out.println(i + " " + sa[i] + " " + str.substring(sa[i]));
		}
	}
	
	public static void sa() {
		length = str.length();
		int m = 127;//通过ASCII码方式确定字符串范围
		
		/* 在倍增之前先进行一次基数排序
		 * x[i]储存str里每一个字符的ASCII码
		 */
		for(int i = 0;i < m;i++) cnt[i] = 0;//开始所有都为0
		for(int i = 0;i < length;i++) cnt[x[i] = str.charAt(i)]++;//通过将字符转换成ASCII码方式对str里面所有字符进行计数
		for(int i = 1;i < m;i++) cnt[i] += cnt[i-1];//从小到大进行编号，为排序做准备。如 str = "aaabba", cnt[a] = 4; cnt[b] = 6; 这时str可被编号为 1 2 3 5 6 4
		for(int i = length-1;i >= 0;i--) sa[--cnt[x[i]]] = i;//sa[i] = j 表示的含义是从小到大排名为i的后缀下标为j，rank数组刚好与sa相反，rank[i] = j表示后缀下标为i的排名为j
		//上行表示的便是对sa数组的求解，这时可用到上一行编号的结果，假如编号已经为 1 2 3 5 6 4，根据排名和下标可得sa数组为 1（编号为1的下标为1，以此类推） 2 3 6 4 5
		
		for(int k = 1;k <= length; k <<= 1) {//倍增
			
			//对第二关键字进行排序
			int p = 0;
			for(int i = length - 1;i >= length - k;i--) y[p++] = i;//相当于补零，由于补的0肯定是最小，因此顺序是最前的
			for(int i = 0;i < length;i++) {
				if(sa[i] >= k) {
					y[p++] = sa[i] - k;
				}
			}
			//例如要排序的数是：92,81,30,24,57,96；
			//对第二关键字排序得到的结果为 y[] = 3,2,1,4,6,5
			//x[y[]] = 30,81,92,24,96,57 表示结果位置上的数
			
			//再一次基数排序，对第一关键字进行排序
			for(int i = 0;i < m;i++) cnt[i] = 0;
			for(int i = 0;i < length;i++) cnt[x[y[i]]]++;
			for(int i = 1;i < m;i++) cnt[i] += cnt[i-1];
			for(int i = length - 1;i >= 0;i--) sa[--cnt[x[y[i]]]] = y[i];
			
			swap();//x和y进行交换
			p = 1;
			x[sa[0]] = 0;
			for(int i = 1;i < length;i++) {
				if(y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i] + k])
	                x[sa[i]] = p-1;
	            else
	                x[sa[i]] = p++;
			}
			if(p >= length) {//当每一个元素都是不同的排名的时候，可以结束循环
				break;
			}
			m = p;
		}
		
	}
	
	public static void swap() {
		int[] tmp = new int[500];
		tmp = x;
		x = y;
		y = tmp;
	}

}


POJ3581：题意为给N个数字序列A1到An，其中A1比其他的数字都大，要将该数字序列分为三段，并将每段分别反转，求得到字典序最小的序列，N <= 200000。

如 N = 5； 序列A = { 10，1，2，3，4 }。

得到结果为  1，10，2，3，4  （分为 {10，1}  {2}  {3，4} 三段，然后反转）

通过离散化和后缀数组模板完成
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	static int[] sa;
	static int[] cnt;
	static int[] x;
	static int[] y;
	static int length;
	static int num;
	static int[] array;
	static final int maxn = 200050;
	static int[] res;
	static int[] ori;
	static node[] n;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		num = in.nextInt();
		n = new node[num];
		array = new int[num];
		res = new int[num];
		ori = new int[num];
		for(int i = num-1;i >= 0;i--) {
			n[i] = new node();
			n[i].number = in.nextInt();
			n[i].id = i;
		}
		Arrays.sort(n);
		for(int i = 0; i< num; i++){
	        if(i != 0 && n[i].number == n[i-1].number)
	        {
	            array[n[i].id] = array[n[i-1].id];
	            continue;
	        }
	        array[n[i].id] = i+1;
	    }
	    
		ori = array;
		sa = new int[maxn];
		cnt = new int[maxn];
		x = new int[maxn];
		y = new int[maxn];
		sa();
		/*
		for(int i = 0;i < length;i++) {
			System.out.print(i + " " + sa[i] + " ");
			for(int j = sa[i];j < num;j++) {
				System.out.print(array[j]);
			}
			System.out.println();
		}
		*/
		
		int p1 = -1;
		for(int i = 0;i < num;i++) {
			p1 = num - sa[i];
			if(p1 >= 1 && num - p1 >= 2) break;
		}
		//System.out.println(p1);
		int count = 0;
		for(int i = num-p1;i < num;i++) {
			res[count] = n[ori[i] - 1].number;
			count++;
		}
		
		int[] t = new int[(num-p1)*2];
		for(int i = 0;i <= 1;i++) {
			for(int j = 0;j < num-p1;j++) {
				t[i*(num-p1) + j] = array[j];
			}
		}

		array = t;
		/*
		for(int i = 0;i < 8;i++) {
			System.out.println(array[i]);
		}*/
		sa();
		/*
		for(int i = 0;i < length;i++) {
			System.out.print(i + " " + sa[i] + " ");
			for(int j = sa[i];j < array.length;j++) {
				System.out.print(array[j]);
			}
			System.out.println();
		}
		*/
		
		int p2 = -1;
		for(int i = 0;i < 2 * (num - p1);i++) {
			p2 = num - sa[i];
			if(p2 - p1 >= 1 && num - p2 >= 1 && sa[i] > 0 && sa[i] < num - p1) {
				break;
			}
		}
		//System.out.println(p2);

		
		for(int i = num - p2;i < num - p1;i++) {
			res[count] = n[ori[i] - 1].number;
			count++;
		}
		for(int i = 0;i < num - p2;i++) {
			res[count] = n[ori[i] - 1].number;
			count++;
		}
		
		for(int i = 0;i < num;i++) {
			System.out.println(res[i]);
		}
		
	}
	
	public static void sa() {
		length = array.length;
		int m = maxn;
		
		for(int i = 0;i < m;i++) cnt[i] = 0;
		for(int i = 0;i < length;i++) cnt[x[i] = array[i]]++;
		for(int i = 1;i < m;i++) cnt[i] += cnt[i-1];
		for(int i = length-1;i >= 0;i--) sa[--cnt[x[i]]] = i;
		
		for(int k = 1;k <= length; k <<= 1) {
			int p = 0;
			for(int i = length - 1;i >= length - k;i--) y[p++] = i;
			for(int i = 0;i < length;i++) {
				if(sa[i] >= k) {
					y[p++] = sa[i] - k;
				}
			}
			
			for(int i = 0;i < m;i++) cnt[i] = 0;
			for(int i = 0;i < length;i++) cnt[x[y[i]]]++;
			for(int i = 1;i < m;i++) cnt[i] += cnt[i-1];
			for(int i = length - 1;i >= 0;i--) sa[--cnt[x[y[i]]]] = y[i];
			
			swap();
			p = 1;
			x[sa[0]] = 0;
			for(int i = 1;i < length;i++) {
				if(y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i] + k])
	                x[sa[i]] = p-1;
	            else
	                x[sa[i]] = p++;
			}
			if(p >= length) {
				break;
			}
			m = p;
		}
		
	}
	
	public static void swap() {
		int[] tmp = new int[maxn];
		tmp = x;
		x = y;
		y = tmp;
	}


}
class node implements Comparable{
	int id;
	int number;
	@Override
	public int compareTo(Object o) {
		node t = (node)o;
		if(this.number > t.number) {
			return 1;
		}else if(this.number == t.number) {
			if(this.id > t.id) {
				return 1;
			}else {
				return -1;
			}
		}else {
			return -1;
		}
	}
	
}