后缀数组的一些基本概念请自行百度。 简单来说，后缀数组是字符串中所有后缀的大小的重新排序。 然后，根据后缀数组的一些性质，可以实现各种需求。
1 publicclassmysuffixarraytest {2}
3公共char [ ] suffix； //原始字符串
4
5公共int n； //字符串长度
6
7公共int [ ] rank； //Suffix[i]在所有后缀中的排名
8
9公共int [ ] sa； //suffix [ sa [1] ] suffix [ sa [2]……suffix [ sa [ len ]，即排名为I的后缀是suffix [ sa [ I ] 10//(什么是rank )
11
12公共int [ ] height； 表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最长公共前缀，即两个相邻后缀的最长公共前缀
13
14公共int [ ] h； //height[rank[I]，即等于后缀Suffix[i]和其上级后缀的最长公共前缀
15
16公共int [ ] ws； //计数排序辅助数组
17
18公共int [ ] y； //第二关键字rank数组
19
20公共int [ ] x； //rank的辅助数组
21 }
以下说明均以' aabaaaab '字符串为例。 首先展示结果，请参考这个结果进行理解分析。 (这个结果图会复制别人的东西，所以请从默认的下标中减去1。 因为我的数组从下标0开始) ) )。
suffix :原始字符串数组假设原始字符串是' aabaaaab '，与此数组对应的值为{'a '、' a '、' b '、' a '、' a '、' a '、' a '、'、' a '、'、'、'
n :字符串长度，其中n是8
rank:后缀数组的顺序数组相当于存储与第I个后缀对应的顺序是多少。 例如，rank[0]是后缀' aabaaaab '的顺序，rank[1]是后缀' abaaaab '的顺序
sa:是与rank数组相反的数组，表示第x个存储了哪个后缀，还是举例说明sa[0]指向第一位的后缀数组。 也就是说，与名为' aaaab '的数组对应的rank[3]为0。 请务必理解sa[rank[i]]=i这个公式。 理解了这个sa和rank的关系后，你应该也明白了
height: height[i]中，sa[i]后缀阵列和sa[i-1]后缀阵列的最大公共前缀的长度height[1]为第2位和第1位的最大公共前缀sa[1]和sa[0]即' sa[0]
h: h[i]是指，第I个后缀和他的上位的最大的共同前缀h[0]是作为第一个后缀排列的' aabaaaab '和他的上位的' aab '的最大的共同前缀的height [ rank [0] ]=height
ws:什么都不说，计数排序的辅助数组
y:包含一个sa数组，其中第二个关键字的排序相当于第二个关键字
x:可以理解为rank数组的备份。 他最初是rank数组的备份，然后记录每个循环的rank数组
首先，让我们看一下求出sa数组的代码。 说明代码的作用，后面附上总代码
1 rank=new int[n]； 2 sa=new int[n]； 3 ws=new int[255]； 4 y=new int[n]； 5 x=new int[n]； 6 //转换循环的原始字符串并将int值放入rank数组
7for(intI=0； i n； I({8rank[I]=(int ) suffix[i]； 9 }
上面代码的作用是初始化数组，进行第一次计数排序。 第一个循环为rank数组指定初始值，执行后的rank数组的对应值为{ 97、97、98、97、97、97、98 }，可以看到rank数组的初始值是与字母对应的ascii代码
接下来的三个循环是第一个计数排序。 不理解计数排序的人请百度。 说一下这三段循环运转的过程
1for(intI=0； i n； I ) {2 ws[rank[i]]； 3x[I]=弗兰克[I]； 4 ) 5for(intI=1； i ws.length； I({6ws[I]=ws[I-1] )； 7 }
这两个循环对所有出现的值进行计数，并将rank数组备份到x数组中。 执行第一个循环后ws[97]=6，ws[98]=2，执行第二个循环后ws[97]=6，ws[98]=8
1for(intI=n-1； i=0； I----}{2sa[--ws]
[rank[i]]] =i;3 }上面这段就是具体的计数排序求sa数组的代码，大家第一次看的时候肯定是蒙的，这怎么就求出了sa呢。我第一次也是蒙的，但请保持耐心，仔细理解这段代码。还记得前面说的公式吗 sa[rank[i]]=i举个例子对于后缀"b"我们求他的sa 即sa[rank[7]]=sa[98]=7，显然sa[98]不存在， 但我们将98出现的次数已经记录在ws数组了(请务必先理解计数排序，否则这里以及之后你都会看不明白)，那么ws[98]应该就是"b"对应的名次了 ，注意不要忘记计数减1 ，就变成了 sa[--ws[rank[i]]] = i(我这里是先减，这也是我的下标比图上少1的原因)。至于为什么要从后向前遍历，这里你需要仔细理解一下，否则后面根据第二关键字进行排序的方式你肯定会完全蒙蔽。如果有两个rank值相同的你怎么排序呢？肯定是先出现的后缀在sa数组的前面，仔细思考这个循环以及ws数组值的变化，你会明白，for循环的顺序实际上代表了rank值相同时的排列顺序。从后向前遍历代表了rank值相同时靠后的后缀排名也靠后。
以上只是第一次计数排序，相当于只比较每个后缀数组的首字母求出了一个sa,对应的结果如下图
1 //循环组合排序
2 for (int j = 1, p = 0; j <= n; j = j << 1) {3 //需要补位的先加入排序数组y
4 p = 0;5 for (int i = n - j; i < n; i++) {6 y[p++] =i;7 }8 //根据第一关键字sa排出第二关键字
9 for (int i = 0; i < n; i++) {10 if (sa[i] >=j) {11 y[p++] = sa[i] -j;12 }13 }14
15 //合并两个关键字的排序
16 for (int i = 0; i < ws.length; i++) {17 ws[i] = 0;18 }19 for (inti : x) {20 ws[i]++;21 }22 for (int i = 1; i < ws.length; i++) {23 ws[i] += ws[i - 1];24 }25 for (int i = n - 1; i >= 0; i--) {26 sa[--ws[x[y[i]]]] =y[i];27 y[i] = 0;28 }29
30 //根据sa算出rank数组
31 int xb[] = new int[n];//x数组备份
32 for (int i = 0; i < n; i++) {33 xb[i] =x[i];34 }35 int number = 1;36 x[sa[0]] = 1;37 for (int i = 1; i < n; i++) {38 if (xb[sa[i]] != xb[sa[i - 1]]) {39 x[sa[i]] = ++number;40 } else if (sa[i] + j >= n && sa[i - 1] + j >=n) {41 x[sa[i]] =number;42 } else if (sa[i] + j < n && sa[i - 1] + j >=n) {43 x[sa[i]] = ++number;44 } else if (xb[sa[i] + j] != xb[sa[i - 1] +j]) {45 x[sa[i]] = ++number;46 } else{47 x[sa[i]] =number;48 }49 if (number >=n)50 break;51 }52 }
上面的代码是循环组合排序，这是求sa数组最难以理解的一段代码，首先大家需要理解一下倍增算法的思路。第一次计数排序后我们是不是已经知道了所有后缀数组第一个首字母的排序，既然我们知道了第一个首字母的排序那是不是相当于我们也知道了他第二个字母的顺序(注意排序和顺序的区别，排序是我们知道他固定的排在第几名，顺序是我们只知道他出现的次序，但并不知道他具体排第几名)，这是当然的,因为他们本来就是出自一个字符串，对于每个后缀他同时也可以作为他之前后缀的后缀。说起来绕口，举个例子，比如对于"baaaab"他首字母的顺序是不是对应"abaaaab"的第二关键字顺序。我们有了第一关键字的排序和第二关键字的排序就能求出两个关键字的组合排序，跟据组合排序的结果我们还是可以延用之前的想法，对于"baaaab"第一次组合排序后我们排出来他头两个字母"ba"的排序，那么他同时他也可以作为"aabaaaab"的第二关键字的顺序。大家应该能看出每次循环关键字都是乘2的关系，这就是倍增算法。整个排序的逻辑参考下图
然后我们来分段的分析代码
1 for (int i = n - j; i < n; i++) {2 y[p++] =i;3 }4 //根据第一关键字sa排出第二关键字
5 for (int i = 0; i < n; i++) {6 if (sa[i] >=j) {7 y[p++] = sa[i] -j;8 }9 }
以上代码就是求第二关键字的sa也就是y数组，p初始值为0，第一段循环是将需要补位的后缀排在数组最前面。这是当然的，需要补位意味着没有第二关键字，自然排在前几名，比如第一次循环时，y[0]=7，也就是第二关键字的第一名是后缀"b"，显而易见，"b"的第二关键字没有所以排在前面。
第二个循环的逻辑你需要结合前面的逻辑图进行理解了，我们对第一关键字的排序结果sa进行遍历(想一下我们为什么对sa进行遍历？sa是已排好的第一关键字排序，遍历他并根据每一个后缀求出他对应的作为第二关键字的后缀自然肯定也是有序的)，if(sa[i] >=j )判断该后缀能否作为其他后缀的第二关键字，以第一次循环j=1为例，当sa[i]=0时代表后缀数组"aabaaaab"，显然它无法作为其他后缀的第二关键字。对于可以作为其他后缀第二关键字的，他sa的顺序就是对应的第二关键字的顺序，sa[i] -j求出他作为第二关键字的后缀放在y数组下，并且p++。这里你需要慢慢理解。
1 //合并两个关键字的排序
2 for (int i = 0; i < ws.length; i++) {3 ws[i] = 0;4 }5 for (inti : x) {6 ws[i]++;7 }8 for (int i = 1; i < ws.length; i++) {9 ws[i] += ws[i - 1];10 }11 for (int i = n - 1; i >= 0; i--) {12 sa[--ws[x[y[i]]]] =y[i];13 y[i] = 0;14 }
以上是根据第一关键字排序sa和第二关键字排序y求出其组合排序，这段代码相当的晦涩难懂。我们可以先不理解代码，先理解一个思路，对于两个关键字排序，实际规则和两个数字排序差不多，比如11和12比较大小，10位就是第一关键字，个位就是第二关键字，比较完10位我们求得11=12，再比较个位我们知道11<12，10位相同的话其个位的顺序就是大小顺序。我上面第一次计数排序时说过，计数排序for循环的顺序实际上代表了rank值相同时的排列顺序，那么这里我们怎么一次计数排序就求出两个关键字合并后的顺序呢？我说下我的理解，一次计数排序实际上包含了两次排序，一次是数值的排序，一次是出现次序的排序，其规则就相当于前面11和12比较的例子，数值的排序是10位，出现次序的排序是个位。到这里我们就有思路了，数值的排序用第一关键字的排序，出现次序的排序用第二关键字的排序，这样就能一次计数排序求得两个关键字合并后的排序。上面的代码就是这个思路的实现。x数组就是第一关键字的rank数组，对x数组计数的过程就是对数值的排序。
1 for (int i = n - 1; i >= 0; i--) {2 sa[--ws[x[y[i]]]] =y[i];3 y[i] = 0;4 }
这第三段循环是上面思路实现的精髓，我们对第二关键字数组y从后进行遍历，这就相当于是出现次序的排序，对于y[i]我们求出他第一关键字的计数排名，这个第一关键字的计数排名就是y[i]的排名，最后计数减1。合并关键字的排序成功求出。
相信你如果理解了上面所有的代码后肯定会拍案叫绝，我本人在一遍遍琢磨这段代码时也是热血澎湃，简直拜服了。这就是算法的魅力吧。
有了sa数组我们就可以求rank数组，这并不难，也就不讲解了。下面附上求sa的所有代码。之后我还会写一篇求height数组的讲解以及后缀数组的一些简单应用。
1 public static voidmain(String[] args) {2 String str = "aabaaaab";3 MySuffixArrayTest arrayTest = newMySuffixArrayTest(str.toString());4 arrayTest.initSa();//求sa数组
5 }6
7 public voidinitSa() {8 rank = new int[n];9 sa = new int[n];10 ws = new int[255];11 y = new int[n];12 x = new int[n];13 //循环原字符串转换int值放入rank数组
14 for (int i = 0; i < n; i++) {15 rank[i] = (int) suffix[i];16 }17 //第一次计数排序
18 for (int i = 0; i < n; i++) {19 ws[rank[i]]++;20 x[i] =rank[i];21 }22 for (int i = 1; i < ws.length; i++) {23 ws[i] += ws[i - 1];24 }25 for (int i = n - 1; i >= 0; i--) {26 sa[--ws[rank[i]]] =i;27 }28 //循环组合排序
29 for (int j = 1, p = 0; j <= n; j = j << 1) {30 //需要补位的先加入排序数组y
31 p = 0;32 for (int i = n - j; i < n; i++) {33 y[p++] =i;34 }35 //根据第一关键字sa排出第二关键字
36 for (int i = 0; i < n; i++) {37 if (sa[i] >=j) {38 y[p++] = sa[i] -j;39 }40 }41
42 //合并两个关键字的排序
43 for (int i = 0; i < ws.length; i++) {44 ws[i] = 0;45 }46 for (inti : x) {47 ws[i]++;48 }49 for (int i = 1; i < ws.length; i++) {50 ws[i] += ws[i - 1];51 }52 for (int i = n - 1; i >= 0; i--) {53 sa[--ws[x[y[i]]]] =y[i];54 y[i] = 0;55 }56
57 //根据sa算出rank数组
58 int xb[] = new int[n];//x数组备份
59 for (int i = 0; i < n; i++) {60 xb[i] =x[i];61 }62 int number = 1;63 x[sa[0]] = 1;64 for (int i = 1; i < n; i++) {65 if (xb[sa[i]] != xb[sa[i - 1]]) {66 x[sa[i]] = ++number;67 } else if (sa[i] + j >= n && sa[i - 1] + j >=n) {68 x[sa[i]] =number;69 } else if (sa[i] + j < n && sa[i - 1] + j >=n) {70 x[sa[i]] = ++number;71 } else if (xb[sa[i] + j] != xb[sa[i - 1] +j]) {72 x[sa[i]] = ++number;73 } else{74 x[sa[i]] =number;75 }76 if (number >=n)77 break;78 }79 }80 }