【经典数据结构】后缀数组

  转自:http://www.acmerblog.com/suffix-array-6150.html

 

  在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。

  后缀树组是一个字符串的所有后缀的排序数组。后缀是指从某个位置 i 开始到整个串末尾结束的一个子串。字符串 r 的从 第 i 个字符开始的后缀表示为 Suffix(i) ,也就是Suffix(i)=r[i..len(r)] 。

  例子:

 1 字符串: "banana"的所有后缀如下:
 2 
 3 0 banana                          5 a
 4 1 anana     对所有后缀排序        3 ana
 5 2 nana      ---------------->     1 anana  
 6 3 ana        字典序               0 banana  
 7 4 na                              4 na   
 8 5 a                               2 nana
 9 
10 所以 "banana" 的后缀数组SA为: {5, 3, 1, 0, 4, 2}

名次数组:名次数组Rank[i]保存的是以i开头的后缀的排名,与SA互为逆。简单的说,后缀数组是“排在第几的是谁”,名次数组是“你排第几”。

构造算法

  求解后缀数组的算法主要有两种:倍增算法DC3算法。在这里使用的是许智磊的倍增算法,复杂度为nlogn。

  关于详细求解后缀数组的算法,详见许智磊2004国家集训队论文

  这里只给出最直接的求解算法,就是先求得所有的后缀子串,再进行一次排序。

  

 1 // 朴素的后缀树组构造算法
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 // 表示一个后缀,index是后缀的开始下标位置
 8 struct suffix
 9 {
10     int index;
11     char *suff;
12 };
13 
14 // 字典序比较后缀
15 int cmp(struct suffix a, struct suffix b)
16 {
17     return strcmp(a.suff, b.suff) < 0? 1 : 0;
18 }
19 
20 // 构造txt的后缀数组
21 int *buildSuffixArray(char *txt, int n)
22 {
23     //结果
24     struct suffix suffixes[n];
25 
26     for (int i = 0; i < n; i++)
27     {
28         suffixes[i].index = i;
29         suffixes[i].suff = (txt+i);
30     }
31 
32     // 排序
33     sort(suffixes, suffixes+n, cmp);
34 
35     // 排在第几的是谁
36     int *suffixArr = new int[n];
37     for (int i = 0; i < n; i++)
38         suffixArr[i] = suffixes[i].index;
39 
40     return  suffixArr;
41 }
42 
43 //打印
44 void printArr(int arr[], int n)
45 {
46     for(int i = 0; i < n; i++)
47         cout << arr[i] << " ";
48     cout << endl;
49 }
50 
51 int main()
52 {
53     char txt[] = "banana";
54     int n = strlen(txt);
55     int *suffixArr = buildSuffixArray(txt,  n);
56     cout << "Following is suffix array for " << txt << endl;
57     printArr(suffixArr, n);
58     return 0;
59 }

输出:

  

1 Following is suffix array for banana
2 5 3 1 0 4 2

如何利用后缀数组来匹配字符串?

在回到那个经典的字符串匹配问题,如何在text中查找模式串pattern?有了后缀数组,我们就可以用二分查找来进行搜索。下面是具体的算法:

  

 1 void search(char *pat, char *txt, int *suffArr, int n)
 2 {
 3     int m = strlen(pat);  
 4 
 5     int l = 0, r = n-1;  
 6     while (l <= r)
 7     {
 8         // 查看 ‘pat‘是否是中间的那个后缀的前缀字串
 9         int mid = l + (r - l)/2;
10         int res = strncmp(pat, txt+suffArr[mid], m);
11 
12         if (res == 0)
13         {
14             cout << "Pattern found at index " << suffArr[mid];
15             return;
16         }
17         if (res < 0) r = mid - 1;
18         else l = mid + 1;
19     }
20     cout << "Pattern not found";
21 }
22 
23 int main()
24 {
25     char txt[] = "banana";  // text
26     char pat[] = "nan";   // 模式串
27 
28     // 构造后缀数组
29     int n = strlen(txt);
30     int *suffArr = buildSuffixArray(txt, n);
31 
32     // 在txt中搜索pat是否出现
33     search(pat, txt, suffArr, n);
34     return 0;
35 }

  上面这个搜索算法的复杂度为O(mLogn),其实还有更高效的基本后缀数组的算法,后续再做讨论。

后缀数组的应用

先定义height数组,height[i] = suffix(SA[i-1])和suffix(SA[i])的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。

技术分享

  例1:最长公共前缀
  给定一个串,求任意两个后缀的最长公共前缀。
  解:先根据rank确定这两个后缀的排名i和j(i<j),在height数组i+1和j之间寻找最小值。(可以用rmq优化)

  例2:最长重复子串(不重叠)(poj1743)
  解:二分长度,根据长度len分组,若某组里SA的最大值与最小值的差>=len,则说明存在长度为len的不重叠的重复子串。

  例3:最长重复子串(可重叠)
  解:height数组里的最大值。这个问题等价于求两个后缀之间的最长公共前缀。

  例4:至少重复k次的最长子串(可重叠)(poj3261)
  解:二分长度,根据长度len分组,若某组里的个数>=k,则说明存在长度为len的至少重复k次子串。

  例5:最长回文子串(ural1297)
  给定一个串,对于它的某个子串,正过来写和反过来写一样,称为回文子串。
  解:枚举每一位,计算以这个位为中心的的最长回文子串(注意串长要分奇数和偶数考虑)。将整个字符串反转写在原字符串后面,中间用$分隔。这样把问题转化为求某两个后缀的最长公共前缀。

  例6:最长公共子串(poj2774)
  给定两个字符串s1和s2,求出s1和s2的最长公共子串。
解:将s2连接到s1后,中间用$分隔开。这样就转化为求两个后缀的最长公共前缀,注意不是height里的最大值,是要满足sa[i-1]和sa[i]不能同时属于s1或者s2。

  例7:长度不小于k的公共子串的个数(poj3415)
  给定两个字符串s1和s2,求出s1和s2的长度不小于k的公共子串的个数(可以相同)。
  解:将两个字符串连接,中间用$分隔开。扫描一遍,每遇到一个s2的后缀就统计与前面的s1的后缀能产生多少个长度不小于k的公共子串,这里s1的后缀需要用单调栈来维护。然后对s1也这样做一次。

  例8:至少出现在k个串中的最长子串(poj3294)
  给定n个字符串,求至少出现在n个串中k个的最长子串。
  将n个字符串连接起来,中间用$分隔开。二分长度,根据长度len分组,判断每组的后缀是否出现在不小于k个原串中。

 

  相关文章:

  1. http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。