后缀数组的学习(四):SA数组实现代码分析

    需要说的都已经在源代码中注明了！

1. #include<stdio.h> 
2. #include<string.h> 
3. #include<algorithm> 
4. using namespace std; 
5. int cmp(int *r,int a,int b,int l){ 
6.     return r[a]==r[b]&&r[a+l]==r[b+l]; 
7. } 
8. #define M 100 
9. int wa[M],wb[M],wv[M],ws[M]; 
10. int SA[M]; 
11.  
12. char s[M]=“aabaaaab”; 
13.  
14. void print(char *label,int *arr,int n){ 
15.     puts(label); 
16.     for(int i=0;i<n;i++) 
17.         printf(“%d “,arr[i]); 
18.     puts(“”); 
19. } 
20. void da(char *r,int *sa,int n,int m){ 
21.      int i, j, p, *x = wa, *y = wb; 
22.      for (i = 0; i < m; i++) 
23.          ws[i] = 0; 
24.      for (i = 0; i < n; i++) 
25.          ws[x[i] = r[i]]++; 
26.      for (i = 1; i < m; i++) 
27.          ws[i] += ws[i – 1]; 
28.      for (i = n – 1; i >= 0; i–) 
29.          sa[–ws[x[i]]] = i; 
30.      print(“array sa:”,sa,n); //**************print************** 
31.  
32.  
33.      for (j = 1, p = 1; p < n; j *= 2,m=p) 
34.      { 
35.          //对第二关键字进行排序:由上一次的结果 直接算出来 
36.          for (p = 0, i = n – j; i < n; i++) y[p++] = i; 
37.          /* 
38.           * y [p++]  表示已经移出表达的范围外面了，所以一定是最小的， 
39.           * 排在前面，但由于我们实际振作的是下标，所以y存储的也是下标， 
40.           * 而且第一个出界的是n-j.实际上排名不分先后 
41.           * 
42.           * 下面的sa[i]-j  即对已经排好序的元素，进行降级处理，表示 
43.           * 及向后移动了j位，实际上这就是后缀的第二关键字  由基数排序 
44.           * 的特点，如果第二关键字有序了，那么排到第一关键字有序的时候， 
45.           * 整个序列就有序了这里我还没有相通的一点是 if(sa[i]>=j)sa[i]-j 
46.           * 这样做了以后，会不会有重复的值出现呢？ 其实不会，这里它把 
47.           * sa[i]值<j的过滤了  我们一定要记住sa[i]储存的是下标，sa[i]小于j，实际 
48.           *  上是最前面的数。 这就有点像滑动窗口的感觉 ！ 指定窗口的大小 
49.           *  为s.size(),窗口以倍增的方式向后滑动，滑动窗口方向 前面 越界 
50.           *  的数值设为0，滑动窗口后面越界的数值扔掉。这样就保证有序了！ 
51.           * 
52.           *  好吧，这段代码花了我几天的时间，如果今天不回头看看 基数 
53.           *  排序，可能还给我几天都搞不懂的！ 唉！基础是硬伤啊！！！ 
54.           * */ 
55.          for (i = 0; i < n; i++) 
56.              if (sa[i] >= j) y[p++] = sa[i] – j; 
57.          print(“array y:”,y,n); //**************print************** 
58.  
59.          //对第一关键字进行排序 
60.          for (i = 0; i < n; i++) wv[i] = x[y[i]]; 
61.          print(“wv:”,wv,n);//************************************** 
62.          /* 
63.           * 如果前面理解了，wv[i]=x[y[i]]也就好理解了 
64.           *实际上：论文里面已经说得很清楚了：x[i]相当于上次排序的rank数组， 
65.               ，而我们的y相当于局部SA数组（只考虑到了一个关键字） 
66.           *如果SA[i]=k,那么一定有 rank[k]=i, 这样的话，这段代码就相当于 rank[sa[i]]=k, 
67.           *就 相当于把数据从小到大扔到待排序的桶里去（联系基数排序来理解 ） 
68.           * */ 
69.         /* 
70.          * 这下面的几行与第一次排序几乎是一模一样的，没有什么好说的 
71.          * 
72.          * */ 
73.          for (i = 0; i < m; i++) ws[i] = 0; 
74.          for (i = 0; i < n; i++) ws[wv[i]]++; 
75.          for (i = 1; i < m; i++) ws[i] += ws[i – 1]; 
76.          for (i = n – 1; i >= 0; i–) sa[–ws[ wv[i]]] = y[i]; 
77.  
78.  
79.          /* 
80.           * 完成排序，通过排序的结果求新的排名 
81.           *  swap(x, y) 这里就不怎么好理解  x[i]相当于上次排序的rank数组， 
82.           *  而我们的y相当于局部SA数组（只考虑到了一个关键字） 
83.           *  交换过后，x就变成局部SA数组了，而y就变成了rank数组 
84.           *   为了思路连贯，方便理解，我把代码调整一下*/ 
85.           //         for (  swap(x, y),p = 1, x[sa[0]] = 0, i = 1; i < n; i++) 
86. //           x[sa[i]] = cmp(y, sa[i – 1], sa[i], j) ? p – 1 : p++; 
87.          for ( p = 1, y[sa[0]] = 0, i = 1; i < n; i++) 
88.             y[sa[i]] = cmp(x, sa[i – 1], sa[i], j) ? p – 1 : p++; 
89.  
90.          swap(x, y); 
91.          /* 
92.           *  这样的话，个人觉得好理解多了！ 
93.           *  首先这几行代码的作用是：通过SA来计算新的rank值 
94.           *   cmp(x, sa[i – 1], sa[i], j) ? p – 1 : p++; 
95.           *   sa[i-1],sa[i]就表示排序后两个相邻的后缀的首地址 
96.           * 
97.           *   x[sa[i-1] ,x[sa[i]]就表示两个排名相邻的元素 
98.           *   其实我个人觉得 x[]数组 既表示了排名，又兼顾表示的原字符串 
99.           *   这里比较抽象，不好理解 
100.           * */ 
101.  
102.      } 
103. } 
104. int main(){ 
105.     int n=strlen(s); 
106.     int m=128; 
107.     da(s,SA,n+1,m); 
108.     print(“sa:”,SA,n+1);//**************print************** 
109.  
110.     return 0; 
111. } 
112. /* 
113.  * sa: 
114.    8 3 4 5 0 6 1 7 2 
115.  * */