https://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/?ref=gcse

后缀数组的$O(nlognlogn)$实现 ，基于倍增和排速

1163. 按字典序排在最后的子串

import java.util.Arrays;

/**
 * @Author: merickbao
 * @Created_Time: 2022-03-23 16:31
 * @Description: 后缀数组 ：https://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/
 */

public class SuffixArray {

	// 后缀数组节点
	class Node implements Comparable<Node> {
		int idx; // 后缀在原始字符串中的起点
		int rank; // 该后缀的排名
		int next; // 第二个比较位的排名

		public Node(int idx, int rank, int next) {
			this.idx = idx;
			this.rank = rank;
			this.next = next;
		}

		@Override
		public int compareTo(Node o) {
			if (o.rank == this.rank) return Integer.compare(this.next, o.next);
			return Integer.compare(this.rank, o.rank);
		}
	}

	public int[] getSuffixArray(String s) {
		int n  = s.length();
		Node[] suffix = new Node[n];
		// 新建节点：最先以单个字母ascii码来排名
		for (int i = 0; i < n; i++) {
			suffix[i] = new Node(i, s.charAt(i) - 'a', 0);
		}
		// 更新下一个节点rank
		for (int i = 0; i < n; i++) {
			// 如果下一个节点超过数组长度，置为-1
			suffix[i].next = (i + 1 < n ? suffix[i + 1].rank : -1);
		}
		// 第一次排序：根据后缀前两位字符排序
		Arrays.sort(suffix);
		// 开始倍增的进行排序 : 4, 8, 16 ...
		int[] ind = new int[n]; // 辅助数组：用来保存下一个比较位的排名
		for (int len = 4; len < 2 * n; len *= 2) {
			// 首先根据排序结果重新分配排名
			int rank = 0, prev = suffix[0].rank;
			suffix[0].rank = 0;
			ind[suffix[0].idx] = 0;
			for (int i = 1; i < n; i++) {
				// 两个节点暂时还不能分出排名，置为相同的排名
				if (suffix[i].rank == prev && suffix[i].next == suffix[i - 1].next) {
					prev = suffix[i].rank;
					suffix[i].rank = rank;
				} else {
					prev = suffix[i].rank;
					suffix[i].rank = ++rank;
				}
				ind[suffix[i].idx] = i;
			}

			// 分配下一个比较位的排名
			for (int i = 0; i < n; i++) {
				int nextP = suffix[i].idx + len / 2;
				suffix[i].next = nextP < n ? suffix[ind[nextP]].rank : -1;
			}

			// 根据前 len / 2 个字符排序
			Arrays.sort(suffix);
		}
		int[] suffixArray = new int[n];
		for (int i = 0; i < n; i++) {
			suffixArray[i] = suffix[i].idx;
		}
		return suffixArray;
	}
}