在介绍后缀数组之前,以字符串"aabaaaab"为例建立两个字符串数组,

1
2
3
4
5
6
String[] before = new String[s.length()];
for(int i = 0; i < before.length; i++) {
before[i] = s.substring(i);
}
java.util.Arrays.sort(before);
String[] after = before;

before数组的内容为,

1
{ "aabaaaab", "abaaaab", "baaaab", "aaaab", "aaab", "aab", "ab", "b" }

对before数组元素按字典序进行排序,得到after数组,

1
{ "aaaab", "aaab", "aab", "aabaaaab", "ab", "abaaaab", "b", "baaaab" }

后缀数组suffix的定义为,after[i]=before[suffix[i]-1],即排第几的元素是什么?

1
{ 4, 5, 6, 1, 7, 2, 8, 3 }

名次数组rank的定义为,before[i]=after[rank[i]-1],即该元素排第几?

1
{ 4, 6, 8, 1, 2, 3, 5, 7 }

height数组保存after数组中相邻元素之间的最长前缀,

1
2
3
4
5
6
7
8
9
10
11
String[] height = new String[after.length];
height[0] = "";
for(int i = 1; i < height.length; i++) {
int x = 0, y = 0;
for(; x < after[i - 1].length() && y < after[i].length(); x++, y++) {
if(after[i - 1].charAt(x) != after[i].charAt(y)) {
break;
}
}
height[i] = after[i - 1].substring(0, x);
}
1
{ "", "aaa", "aa", "aab", "a", "ab", "", "b" }
可重叠最长重复子串

即为height数组中length最大的元素,"aaa""aab"

最长回文子串

将原字符串翻转后拼接到原字符串末尾,中间用特殊字符(如$)隔开,得到新的字符串"aabaaaab$baaaabaa",新字符串的height数组为,

1
{ "", "", "a", "aa", "aaaab", "aaa", "aaab", "aa", "aab", "aabaa", "a", "ab", "abaa", "", "b", "baa", "baaaab" }

最长回文子串即为height数组中length最大的元素,"baaaab"