后缀数组 Suffix Array 及最长公共前缀 LCP 理论及应用

摘要：本文主要是记录后缀数组 Suffix Array 及最长公共前缀 LCP 理论及应用。首先讲解概念，然后介绍简单的 Java 实现，最后列举若干实际问题的应用。

概念

符号定义

待研究字符串：$S$
字符串长度：$n$
其中字符串的字符序列表示为 ${s_1,s_2,s_3…s_n}$ 下标用 $i$ 表示
$S$ 的后缀数组：$Suffix(S)$ 其元素简写为 $sa[i]$
$S$ 的名次数组：$Rank(S)$ 其元素简写为 $rank[i]$

后缀数组

首先我们要了解是什么是 字符串后缀，字符串后缀就是从字符串的某个位置开始到字符串末尾的子串。所以一个字符串$S$，其字符串后缀的数目是 $n$，就是其长度 $Length(S)$。

后缀数组：指将某个字符串的所有后缀按照字典序排序后得到的数组，但数组并不直接保存后缀字符串，只保存对应的其实位置。直观上后缀数组是字符串 $S$ 所有的字符串后缀组成的数组，但是这样十分浪费空间，所以这里进行了优化，通过上面字符串后缀的定义，我们知道$S$的字符串后缀，实际上就是从字符串字符下标 $0$ 开始，一直到 $n-1$。我们完全可以使用这些 index 在 $O(n)$ 的复杂度获取这些字符串后缀。所以我们只需要存储对应的字符串后缀首字符下标，也就是其位置。

关于 Java 字串时间复杂度，这里说明一下，在 Java7 update 6 之前是常数时间，但是之后变成了 $O(n)$，因为修复了substring 的内存泄露问题，参考：Stack Overflow 和第四版算法给出的链接：Changes to String internal representation made in Java 1.7.0_06

什么是按照字典顺序？

字符串的比较：两个字符串大小的比较，从首位开始，一位一位地按照 ASCII 码比较，如果从某位置开始不相同，则认为该位置处字符 ASCII 码小的字符串小；如果一个字符串比较完了最后一位，而另一个没有，则认为前者（长度小的）小；如果两个字符串长度相同并且所有位置上的字符均相同，则认为两个字符串相等。

注意，同一个字符串的两个后缀是不可能相等的，因为无法满足相等的必要条件长度相同。

什么是名次数组 rank

名次数组保存的是后缀数组在所有后缀从小到大排列的名次。

简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。容易看出，后缀数组和名次数组为互逆运算。

下图清楚的解释了两者之间的关系

简单解释一下，我们看到 $sa[1]$ 是 4，表示从下标为 4（这里下标从1开始）的后缀字符串的字典顺序排在第一位，那么 $rank[4]$ 就是 1。我们清楚的看到了其关系正式互逆的，也就是 index 和 value 是互逆的。知道任何一个，都可以在 $O(n)$ 的复杂度下求出另外一个。

这一点是倍增算法的基础，倍增算法就是先求出 $Rank(s)$ 然后求 $Suffix(s)$。

最长公共前缀（LCP）数组

最长公共前缀数组： Longest Common Prefix Array

最长公共前缀：根据名字我们很好理解，就是指两个字符串，从下标为0开始的前缀，找到完全相同的部分，而且是越长越好。在后缀数组的应用场景下，字符串就是指所有的后缀字符串。

最长公共前缀数组：就是由后缀数组中相邻两个后缀的最长公共前缀的长度组成的数组。

但是这里有个问题：究竟是和前一个比还是后一个呢？，在 Algorithm 4th Edition 的代码是和前一个比，而这篇博文是和后一个比的。这个问题不难回答，因为不论怎么比，其 LCP 序列的相对顺序是固定的，只是开头和结尾是否有效的问题：

和后面的后缀字符串比，那么最后一个将无效。
和前面的后缀字符串比，那么第一个将无效。

下面的表格清楚的表示了两种求 LCP 的方法的结果， lcpN表示和后一个进行比较 N 表示 Next。

===============================
  i ind lcp lcpN rnk select
---------------------------
  0  10   -   1   0 "a"
  1   7   1   4   1 "abra"
  2   0   4   1   2 "abracadabra"
  3   3   1   1   3 "acadabra"
  4   5   1   0   4 "adabra"
  5   8   0   3   5 "bra"
  6   1   3   0   6 "bracadabra"
  7   4   0   0   7 "cadabra"
  8   6   0   0   8 "dabra"
  9   9   0   2   9 "ra"
 10   2   2   -  10 "racadabra"
===============================

实现

理论

倍增算法求解后缀数组

倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为$2^k$的子字符串进行排序，求出排名，即$rank$值。$k$从$0$开始，每次加$1$，当$2^k$大于$n$以后，每个字符开始的长度为$2^k$的子字符串便相当于所有的后缀。并且这些子字符串都一定已经比较出大小，即$rank$值中没有相同的值，那么此时的$rank$值就是最后的结果。每一次排序都利用上次长度为$2^k-1$的字符串的$rank$值，那么长度为$2^k$的字符串就可以用两个长度为$2^k-1$的字符串的排名作为关键字表示，然后进行基数排序，便得出了长度为$2^k$的字符串的$rank$值。以字符串“aabaaaab”为例，整个过程下图所示。其中$x$、$y$是表示长度为$2^k$的字符串的两个关键字。

这里需要双基数的排序。

倍增算法的时间复杂度比较容易分析。每次基数排序的时间复杂度为$O(n)$，排序的次数决定于最长公共子串的长度，最坏情况下，排序次数为logn次，所以总的时间复杂度为$O(nlogn)$。

倍增算法 Java 实现

倍增算法的 Java 实现：Manber.java

java 的实现中有一点优化，初始 rank的时候统计了一下字符出现的频率。

为了和上面的例子对比，这里打印出实现处理的结果，注意这里下标是以 0 开始的，所以和上图比较的时候自行加1.

- String: aabaaaab
- after sort by leading char:
- rank[n]: [0, 0, 6, 0, 0, 0, 0, 6, -1]  按照字符频率，a 出现了6次，所以 a 是0，b 就是 0+6=6.
- index[n]: [0, 1, 3, 4, 5, 6, 2, 7, 8]
- start do it:
- rank: [0, 4, 6, 0, 0, 0, 4, 6, -1]
- rank: [0, 4, 7, 0, 0, 0, 4, 6, -1]
- rank: [3, 4, 7, 0, 1, 2, 4, 6, -1]
- rank: [3, 5, 7, 0, 1, 2, 4, 6, -1]
- final rank: [3, 5, 7, 0, 1, 2, 4, 6, -1]
- after do it:
- rank[n]: [3, 5, 7, 0, 1, 2, 4, 6, -1]
- index[n]: [3, 4, 5, 0, 6, 1, 7, 2, 8]
   i  ind     select
------------------------
   0    3  "aaaab"
   1    4  "aaab"
   2    5  "aab"
   3    0  "aabaaaab"
   4    6  "ab"
   5    1  "abaaaab"
   6    7  "b"
   7    2  "baaaab"

Java 朴素代码

朴素后缀数组求解

这里介绍一种较为简单的算法，记住 Java 内置的 sort 朴素的计算，该方法来自 Algorithm 4th。发方法比较好理解，好记忆，同时能够通过 Hackerrank 的相关题目。

定义 Suffix

public static class Suffix implements Comparable<Suffix> {
	private final String text;
	private final int index;

	public Suffix(String text, int index) {
		this.text = text;
		this.index = index;
	}
	private int length() {
		return text.length() - index;
	}
	private char charAt(int i) {
		return text.charAt(index + i);
	}
		
	//这里是字典顺序排序的实现
	// 如果当前字符串 字典小于 that 字符串，返回 -1
	// 如果当前字符串 字典大于 that 字符串，返回 1
	// 如果当前字符串 字典等于 that 字符串，返回 0
	// 这种返回的模式适用于 升序排序。
	// 倒序排序：
	// Arrays.sort(suffixes, Collections.reverseOrder());
	// public int compare(Comparable<Object> c1, Comparable<Object> c2) {
    //        return c2.compareTo(c1);
    //    }
	// 实际上就是比较的时候 互换一下，自然结果就倒过来了。
	
	public int compareTo(Suffix that) {
		if (this == that) return 0;  // optimization
		int n = Math.min(this.length(), that.length());
		for (int i = 0; i < n; i++) {
			if (this.charAt(i) < that.charAt(i)) return -1;
			if (this.charAt(i) > that.charAt(i)) return +1;
		}
		return this.length() - that.length();
	}

	public String toString() {
		return text.substring(index);
	}
}

Suffix 需要实现 Comparable，因为我们需要对其进行比较。它有两个成员，一个是字符串，一个是 index，给定这两个值，我们就可以通过 toString 方法拿到该 Suffix，toString 调用了 Java 内置的 text.substring(index)。

另外实现比较方法，该方法不仅负责比较字典顺序，还要比较长度，因为一个字符的后缀字符串长度肯定是不同，所以一定能比出大小，因为即使参考短的的后缀字符串所有字符都一直，但是通过 this.length() - that.length() 还是可以分出大小：短的小，长的大（也就是说 aaa 大于 aa，符合字典顺序）

另外两个工具方法：

返回长度，只需要用整个字符长度减去 index 前面的字符数目即可
返回位置 i 的 char，只需要在 index 基础上寻找 i 即可

定义 SuffixArray

这个累就是关键了

public class SuffixArray {
	private Suffix[] suffixes;

    public Suffix[] getSuffixes() {
        return suffixes;
    }
	
	/**
     * Initializes a suffix array for the given {@code text} string.
     * @param text the input string
     */
    public SuffixArray(String text) {
        int n = text.length();
        this.suffixes = new Suffix[n];
        for (int i = 0; i < n; i++)
            suffixes[i] = new Suffix(text, i);
        Arrays.sort(suffixes);
    }
}

首先有一个成员变量，就是 Suffix 的数组。然后是构造函数：传入一个字符串，然后将初始化字符串长度的 Suffix 数组，并用 $O(n)$ 复杂度初始化每一个 Suffix，起始位置就是字符串字符下标。然后用 Arrays.sort(suffixes) 对其进行排序，因为我们已经定义了按照字典排序的比较函数，所以操作后就是字典顺序了。

实际上这时候我们的 SuffixArray 就已经构造好了。

下面介绍一些工具方法：

比较字符串和 `Suffix`

这里提供两种概念的比较，原始代码只有一种完全比较。这里提供一种包含比较。

1. 完全比较

就是无论是字典顺序还是长度都需要比较。该比较方法能够判断输入的字符串将会位于 Suffix 的哪一侧。完全相同返回 0，否则先按照字典顺序，如果字典顺序无法分出胜负，那么如果输入字符串短，返回-1，长返回+1

private static int compare(String query, Suffix suffix) {
	// only compare the min size of two string.
	int n = Math.min(query.length(), suffix.length());
	for (int i = 0; i < n; i++) {
		if (query.charAt(i) < suffix.charAt(i)) return -1;
		if (query.charAt(i) > suffix.charAt(i)) return +1;
	}
	// 关键，比较了长度 query less than suffix，-1
	return  query.length() - suffix.length();
}

2. 包含比较

就是之比较输入字符串部分的字典顺序，只要 Suffix 能够包含输入字符串，就返回 0，否则返回 -1 或 +1。该方法用于搜索字符串是否在 Suffix 中出现使用。

private static int compareSearch(String query, Suffix suffix) {
    // only compare the min size of two string.
    int n = Math.min(query.length(), suffix.length());
    for (int i = 0; i < n; i++) {
        if (query.charAt(i) < suffix.charAt(i)) return -1;
        if (query.charAt(i) > suffix.charAt(i)) return +1;
    }
    return 0;
}

和字符串关系

通过上面提到的两种比较方法，就能够有两种和字符串比较的关系：字符串在 Suffix 中的位置和字符串是否是子串：

全部使用二分法 Binary Search 查找。

public int rank(String query) {
	int lo = 0, hi = suffixes.length - 1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		// lo + hi/2 -lo/2 = lo/2+hi/2
		int cmp = compare(query, suffixes[mid]);
		if (cmp < 0) hi = mid - 1;
		else if (cmp > 0) lo = mid + 1;
		else return mid;
	}
	return lo;
}

public boolean check(String query) {
	int lo = 0, hi = suffixes.length - 1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		int cmp = compareSearch(query, suffixes[mid]);
		if (cmp < 0) hi = mid - 1;
		else if (cmp > 0) lo = mid + 1;
		else return true;
	}
	return false;
}

计算 LCP

/**
 * Returns the length of the longest common prefix of the <em>i</em>th
 * smallest suffix and the <em>i</em>-1st smallest suffix.
 * @param i an integer between 1 and <em>n</em>-1
 * @return the length of the longest common prefix of the <em>i</em>th
 * smallest suffix and the <em>i</em>-1st smallest suffix.
 * @throws IllegalArgumentException unless {@code 1 <= i < n}
 */
public int lcp(int i) {
	if (i < 1 || i >= suffixes.length) throw new IllegalArgumentException();
	return lcpSuffix(suffixes[i], suffixes[i-1]);
}

/**
 * Compute the lcp between i with i+1
 *
 * @param i  an integer between 1 and <em>n</em>-1
 * @return the length of the longest common prefix of the <em>i</em>th
 *         smallest suffix and the <em>i+1</em>st smallest suffix.
 */
public int lcpNext(int i) {
	if (i < 0 || i > suffixes.length) {
		throw new IllegalArgumentException();
	}
	return lcpSuffix(suffixes[i + 1], suffixes[i]);
}

// longest common prefix of s and t
private static int lcpSuffix(Suffix s, Suffix t) {
	int n = Math.min(s.length(), t.length());
	for (int i = 0; i < n; i++) {
		if (s.charAt(i) != t.charAt(i)) return i;
	}
	return n;
}

这里注意 LCP 可以和前一个比，也可以和后一个比较。前面已经介绍了其结果，不在赘述，需要根据需要使用对应的 LCP。

应用

说了这么多理论，这个 Suffix Array 和 LCP 到底能干什么？我们先来几道算法菜压压惊。

Distinct Substrings

https://www.spoj.com/problems/DISUBSTR/

Given a string, we need to find the total number of its distinct substrings.

Input T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 1000

Output For each test case output one number saying the number of distinct substrings.

简单的说就是寻找一个字符串所有可能的并且完全不同的子字符串的数目。

这个题目如果从表面上解答，需要遍历所有可能的子串，然后用一个 Set 来保存，如果重复了就自动覆盖，但是这样做的复杂度是 $O(n^2)$，效率低下，下面我们就来简要介绍一下使用 Suffix Array 和 LCP 的解法：参考解答方法：Given a string, how do I find the number of distinct substrings of the string?

这里只给出思路，具体解决可以查看上面的链接。

若干推论

首先我给出几个推论（不一定严谨）

所有可能的字串的开头一定一定数目的字符（至少是1个）和 Suffix Array 某个字符串匹配。Suffix Array 包含了所有可能的开头的字串。
相邻两个 $Suffix[i]$ 和 $Suffix[i+1]$ 的 LCP 最大值只能是 $Suffix[i]$ 的长度，也就意味着 $Suffix[i+1]$ 只比 $Suffix[i]$ 多一个字符，前面的字符完全一致。假设 $Suffix[i]$ 能够构造的 Distinct String 数目（必须从头开始，不能从中间开始）为 $k$，那么 $Suffix[i+1]$ 也只能再多构造 $1$ 个子串。比如 ana 和 anaa，ana 能够构造 a，an，ana，而 anaa，只能够再构造 anaa，其他的从头开始的子串都已经被 ana 构造的覆盖了。
通过上面的推论我们进一步延伸，如果 $Suffix[i]$ 和 $Suffix[i+1]$ 的 LCP 为 $l$，$Suffix[i]$ 能够构造的 Distinct String 数目（必须从头开始，不能从中间开始）为 $k$，那么 $Suffix[i+1]$ 也只能再多构造 $Cal(l)= (Length_{Suffix[i+1]}-l)$ 个子串..比如 ana 和 anaab，LCP 为 $3$, anaab 长度为 $5$，所以 anaab 能多构造的子串为：$5-3=2$ ana 能够构造 a，an，ana，而 anaab，只能够再构造 anaa, anaab，其他的从头开始的子串都已经被 ana 构造的覆盖。
为什么我们不会从 Suffix 寻找不从头开始的子串呢？因为我们 Suffix Array 会覆盖所有可能的起始子字符串（因为这个集合是从 index=0，然后逐步累加获取的子串），所以当前 Suffix Array 从中间开始的子串，必然会在其他的 Suffix 中出现，或者说是字典顺序靠后的子串中出现。比如 banana 的 Suffix Array
1
2
3
4
5
6
5) A
3) ANA 我们不用尝试获取 NA，
1) ANANA
0) BANANA
4) NA 因为 NA 在这里还会被匹配到
2) NANA

求解思路

找到 Suffix Array，并计算每个 Suffix 和下一个的 LCP。
子串数目初始化为 0
遍历 Suffix Array，根据 LCP 计算该 Suffix 能贡献的 Distinct String 的数目，加入总数。

LCP 和下一个 Suffix 比较
贡献值	  Length	LCP  Index String     子串
1		1		  1	   5)    A   			A
3-1=2	3		  3	   3)    ANA			AN  ANA
5-3=2	5		  0	   1)    ANANA   		ANAN ANANA
6=0=6	6		  0	   0)    BANANA   		B BA BAN BANA BANAN BANANA
2-0=2	2		  2	   4)    NA   			N NA
4-2=2	4		  -	   2)    NANA   		NAN NANA

累加左侧贡献值
1+2+2+6+2+2=15

同时我们观察左侧的子串还有另外一个福利，那么从上到下，从左到右，这些子串也是按照字典顺序排列的。这一点也是因为根据推论4，我们没有随便从 Suffix 中间开始的子串求出来，因为这些子串如果存在，必然会在字典顺序靠后的 Suffix 存在，并且开头和 Suffix 对齐。

Ashton and String

https://www.hackerrank.com/challenges/ashton-and-string/editorial

这是一道 Advance 的算法题，但是根据我们上一道题目的福利部分，这道题超级简单了。

简单的说，题目就是给定一个字符串，找到所有的 Distinct String 后，将其按照字典顺序连接，然后给定一个整数，然后从连接的最终字符串中找到整数对应的字符。

根据上面的题目我们已经能够迭代出每个 Suffix 能够按照字典顺序贡献的子串，同时这些子串的长度也是有规律，

LCP 和下一个 Suffix 比较
贡献值	  Length	LCP  Index String     子串 及长度序列 			
1		1		  1    5)    A   			A 0+1  
3-1=2	3		  3    3)    ANA			AN ANA 1+1 1+2 <= <= length
5-3=2	5		  0    1)    ANANA   		ANAN ANANA 3+1 3+2=5 <= length
6=0=6	6		  0    0)    BANANA   		B BA BAN BANA BANAN BANANA 1,2,3,4,5
2-0=2	2		  2    4)    NA   			N NA 1,2
4-2=2	4		  -    2)    NANA   		NAN NANA 3,4

累加左侧贡献值
1+2+2+6+2+2=15

其每个 Suffix 贡献的子串的长度序列就是从 $LCP(i-1)+1$ 开始累加直到 Suffix 字符串长度 $Length(i)$，比如 ANANA ，上一个 LCP 为 3，所以从 3 开始累加一直累加到 5.

代码实现伪代码

目标位置  
int target = k
当前已经累加的子串长度： 
int currentLength = 0

开始遍历每一个 Suffix，i 为下标
	获取前一个 lcp ：int lcpPreviousI = i == 0 ? 0 : suffix.lcpNext(i - 1);
	// 注意这里对于第一个元素，我们返回0
	获取当前的 Suffix 长度： int lengthI = suffix.getSuffixes()[i].length();
	开始迭代 （上一个 lcp+1 一直到当前 suffix length）
	int p = lcpPreviousI;
    while (p < lengthI) {
		这个 lcp+1的逐步累加，实际就表示我们需要去除的子串的结尾下标
        int currentSubLength = p + 1;
		取出当前子串
		String sub = suffix.getSuffixes()[i].toString().substring(0, p + 1);
		将子串长度加入到全局累加的长度
		currentLength += currentSubLength;
		判断是否已经达到要求
		if (currentLength >= k) {
			如果达到要求，说明目标的字符肯定就在当前这个子串中，那么如何计算位置呢？
			首先计算当前 currentLength 超出了目标 k 值多少，然后在当前子串中从后面将这部分剔除，所以实际需要的子串的长度就是 sub.length() - (currentLength - k)，如果我们想取出左后一个字符，只需要获取 sub.charAt(sub.length() - (currentLength - k) - 1) 即可。
			return sub.charAt(sub.length() - 1 - (currentLength - k));
		}
	p++
i++

代码实现 Java 8 代码

完整解决 Java 代码，（全部通过 Java 8）

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
import java.util.stream.Collectors;

public class Solution {

    /*
     * Complete the ashtonString function below.
     */
//################################## Suffix Array Start #####################################

    public static class Suffix implements Comparable<Suffix> {

        private final String text;
        private final int index;

        private Suffix(String text, int index) {
            this.text = text;
            this.index = index;
        }

        private int length() {
            return text.length() - index;
        }

        private char charAt(int i) {
            return text.charAt(index + i);
        }

        public int compareTo(Suffix that) {
            if (this == that) {
                return 0;  // optimization
            }
            int n = Math.min(this.length(), that.length());
            for (int i = 0; i < n; i++) {
                if (this.charAt(i) < that.charAt(i)) {
                    return -1;
                }
                if (this.charAt(i) > that.charAt(i)) {
                    return +1;
                }
            }
            return this.length() - that.length();
        }

        public String toString() {
            return text.substring(index);
        }
    }

    public static class SuffixArray {

        private Suffix[] suffixes;

        Suffix[] getSuffixes() {
            return suffixes;
        }

        /**
         * Initializes a suffix array for the given {@code text} string.
         *
         * @param text the input string
         */
        SuffixArray(String text) {
            int n = text.length();
            this.suffixes = new Suffix[n];
            for (int i = 0; i < n; i++) {
                suffixes[i] = new Suffix(text, i);
            }
            Arrays.sort(suffixes);
        }


        /**
         * Returns the length of the input string.
         *
         * @return the length of the input string
         */
        public int length() {
            return suffixes.length;
        }


        /**
         * Returns the index into the original string of the <em>i</em>th smallest suffix.
         * That is, {@code text.substring(sa.index(i))} is the <em>i</em>th smallest suffix.
         *
         * @param i an integer between 0 and <em>n</em>-1
         * @return the index into the original string of the <em>i</em>th smallest suffix
         * @throws IllegalArgumentException unless {@code 0 <= i < n}
         */
        public int index(int i) {
            if (i < 0 || i >= suffixes.length) {
                throw new IllegalArgumentException();
            }
            return suffixes[i].index;
        }


        /**
         * Returns the length of the longest common prefix of the <em>i</em>th
         * smallest suffix and the <em>i</em>-1st smallest suffix.
         *
         * @param i an integer between 1 and <em>n</em>-1
         * @return the length of the longest common prefix of the <em>i</em>th
         *         smallest suffix and the <em>i</em>-1st smallest suffix.
         * @throws IllegalArgumentException unless {@code 1 <= i < n}
         */
        public int lcp(int i) {
            if (i < 1 || i >= suffixes.length) {
                throw new IllegalArgumentException();
            }
            return lcpSuffix(suffixes[i], suffixes[i - 1]);
        }

        public int lcpReverse(int i) {
            if (i < 0 || i > suffixes.length) {
                throw new IllegalArgumentException();
            }
            return lcpSuffix(suffixes[i + 1], suffixes[i]);
        }

        // longest common prefix of s and t
        private static int lcpSuffix(Suffix s, Suffix t) {
            int n = Math.min(s.length(), t.length());
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) != t.charAt(i)) {
                    return i;
                }
            }
            return n;
        }

        /**
         * Returns the <em>i</em>th smallest suffix as a string.
         *
         * @param i the index
         * @return the <em>i</em> smallest suffix as a string
         * @throws IllegalArgumentException unless {@code 0 <= i < n}
         */
        public String select(int i) {
            if (i < 0 || i >= suffixes.length) {
                throw new IllegalArgumentException();
            }
            return suffixes[i].toString();
        }

        /**
         * Returns the number of suffixes strictly less than the {@code query} string.
         * We note that {@code rank(select(i))} equals {@code i} for each {@code i}
         * between 0 and <em>n</em>-1.
         *
         * @param query the query string
         * @return the number of suffixes strictly less than {@code query}
         */
        public int rank(String query) {
            int lo = 0, hi = suffixes.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int cmp = compare(query, suffixes[mid]);
                if (cmp < 0) {
                    hi = mid - 1;
                } else if (cmp > 0) {
                    lo = mid + 1;
                } else {
                    return mid;
                }
            }
            return lo;
        }

        // compare query string to suffix
        private static int compare(String query, Suffix suffix) {
            // only compare the min size of two string.
            int n = Math.min(query.length(), suffix.length());
            for (int i = 0; i < n; i++) {
                if (query.charAt(i) < suffix.charAt(i)) {
                    return -1;
                }
                if (query.charAt(i) > suffix.charAt(i)) {
                    return +1;
                }
            }
            return query.length() - suffix.length();
        }
    }

    //################################## Suffix Array End #####################################



    /*
    Ashton appeared for a job interview and is asked the following question.
    Arrange all the distinct substrings of a given string in lexicographical order and concatenate them.
    Print the K character of the concatenated string. It is assured that given value of K will be valid
    i.e. there will be a Ks character. Can you help Ashton out with this?

    For example, given the string abc, its distinct substrings are [a, ab, abc, b, bc, c].
    Sorted and concatenated, they make the string .
    If  then, the answer is , the  character of the 1-indexed concatenated string.
    * */

    /*
     * Complete the ashtonString function below.
     */
    static char ashtonString(String s, int k) {
        /*
         * Write your code here.
         */
        // calculate the suffix array and lcp
        SuffixArray suffix = new SuffixArray(s);

        // the initial index to process the suffix
        int i = 0;
        int currentLength = 0;

        while (i < suffix.getSuffixes().length) {
            // current lcp i
            // int lcpI = suffix.lcp(i);
            // previous lcp i-1
            int lcpPreviousI = i == 0 ? 0 : suffix.lcpReverse(i - 1);
            // length of suffix i
            int lengthI = suffix.getSuffixes()[i].length();

            int p = lcpPreviousI;

            while (p < lengthI) {
                int currentSubLength = p + 1;
                String sub = suffix.getSuffixes()[i].toString().substring(0, p + 1);
                currentLength += currentSubLength;
                // if we have handled enough chars
                if (currentLength >= k) {
                    return sub.charAt(sub.length() - 1 - (currentLength - k));
                }
                p++;
            }
            i++;
        }
        return 'a';
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String s = scanner.nextLine();

            int k = Integer.parseInt(scanner.nextLine().trim());

            char res = ashtonString(s, k);

            bufferedWriter.write(String.valueOf(res));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

参考资料

后缀数组——处理字符串的有力工具/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2009%E8%AE%BA%E6%96%87%E9%9B%86/11.%E7%BD%97%E7%A9%97%E9%AA%9E%E3%80%8A%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E2%80%94%E2%80%94%E5%A4%84%E7%90%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%9C%89%E5%8A%9B%E5%B7%A5%E5%85%B7%E3%80%8B/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E2%80%94%E2%80%94%E5%A4%84%E7%90%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%9C%89%E5%8A%9B%E5%B7%A5%E5%85%B7.pdf) 这篇论文讲解的是最透彻的。网页版无图
后缀数组学习笔记
后缀数组的实现和字符串匹配
LCP数组的实现和最长公共连续子串
Ashton-and-String-topic
Geeksforgeeks-suffix-array
Suffix arrays:A new method for on-line string searches 倍增算法论文
Suffix Arrays Algorithm 第4版针对 Suffix Array 页面，有很多资源。比如 Manber’s algorithm 就是倍增算法的 Java 实现，以及 Suffix 的 Java 实现 SuffixArray Java
Algorithms, 4th edition textbook code and libraries
Algorithms 4th Edition

概念