首页 > 代码库 > 后缀数组之构建的一目了然说明

后缀数组之构建的一目了然说明

2024-07-01 22:29:47   224人阅读

什么是后缀数组？

后缀数组是一种解决字符串问题的有力工具。相比于后缀树，它更易于实现且占用内存更少。在实际应用中，后缀数组经常用于解决字符串有关的复杂问题。

先介绍几个后缀数组中的基本定义：

子串：字符串S 的子串r[i..j]，i≤j，表示r 串中从i 到j 这一段，也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串。
后缀：后缀是指从某个位置i 开始到整个串末尾结束的一个特殊子串。字符串r 的从第i 个字符开始的后缀表示为Suffix(i) ， 也就是Suffix(i)=r[i..len(r)]。
有点不明白了吧？
来看个简单的后缀数组的构建代码就知道大概是个什么东西了
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] getSuffixArray(String str) { 
 
if (str == null) return null; 
 
// 初始化后缀数组 
String[] suffix = new String[str.length()]; 
 
for (int i = 0; i < suffix.length; i++) 
suffix[i] = str.substring(i);  
 
// 对后缀数组排序 
Arrays.sort(suffix);  
 
// 求结果数组 
int[] result = new int[str.length()];
for (int i = 0; i < suffix.length; i++) { 
result[i] = str.lastIndexOf(suffix[i]); 
}  
 
return result; 
}

　　返回的result数组就是名次数组，意思就是“排第几的是谁？”。

以上面代码为例，假设str="abracadabra"

则suffix[]={

"abracadabra",

 "bracadabra",

   "racadabra",

    "acadabra",

     "cadabra",

      "adabra",

       "dabra",

        "abra",

         "bra",

           "ra",

            "a",

             ""

}

然后对suffix数组排序后，结果：

 排完序后，后缀数组表示的意思就是“排第几的是谁？”

接下来result数组就是

 

result数组表示的意思就是“你排第几？”。

三步中如何对suffix数组排序是最费时的，有一些算法用于处理这事（Ukkonen 算法，DC3 算法，倍增算法等）

后缀数组应用

例1：给定一个字符串，求最长重复子串，这两个子串可以重叠。

相邻suffix数组匹配的最长长度

例2：给定两个字符串A 和B，求最长公共子串

先将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组，再求最长公共子串


联系
我们