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

 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}

 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

 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 }