转载自 ： http://blog.csdn.net/j_sure/article/details/41777097

后缀数组学习笔记【详解】

老天，一个后缀数组不知道看了多少天，最后终于还是看懂了啊！

最关键的就是一会儿下标表示排名，一会用数值表示排名绕死人了。

我不知道手跑了多少次才明白过来。其实我也建议初学者手跑几遍，但是一定要注意数组的意义，否则就是无用功。

数组含义：

s[ ]：输入的字符串，预处理的时候会在末尾加上一个0

sa[ ]：它的下标就是后缀排名

x[ ] = t[ ]：用来保存第一关键字排名，注意！它的数值是排名。初始时恰好是字符串的ASCII码。字典序嘛！

y[ ] = t2[ ]：它的下标就是第二关键字排名，第二关键字是直接从sa[ ]当中提取的，关系极其密切

c[ ]：用来基数排序。初始值恰好是每种字符出现的次数。后来它的作用就跟基数排序密切相关，建议学习基数排序

有一点一定要注意！第二关键字来自sa[ ]数组，但是第一关键字并不是来自sa[ ]数组！这一点不知道迷惑了多少人，就是因为论文里给出的图完全就是原理图，不是代码实现的图，不搭噶的！

P.S. 为了优化时间空间，避免新开一个中间数组来复制t[ ]的值，采用了将它的指针x和t2[ ]的指针y交换的方法。注意这个时候t2[ ]已经没有用了。

我先给出一个足以理解后缀数组的增加了中间输出的代码：

[cpp]  view plain  copy
 print ?
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <algorithm>  
  4. using namespace std;  
  5. const int N = 1000, M = 130;  
  6. char s[N];  
  7. int sa[N], t[N], t2[N], c[M], n;  
  8. int rank[N], high[N];  
  9.   
  10. #define DBG  
  11. #ifdef DBG  
  12. int db[N];  
  13. void debug(int *f)  
  14. {  
  15.     for(int i = 0; i < n; i++) {  
  16.         db[f[i]] = i;  
  17.     }  
  18.     printf("%3d", db[0]);  
  19.     for(int i = 1; i < n; i++) {  
  20.         printf(" %3d", db[i]);  
  21.     }puts("]");  
  22. }  
  23. #endif  
  24.   
  25. bool cmp(int *y, int i, int k)  
  26. {  
  27.     return y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k];  
  28. }  
  29.   
  30. void build(int m)  
  31. {  
  32.     int i, *x = t, *y = t2;  
  33.     for(i = 0; i < m; i++) c[i] = 0;  
  34.     for(i = 0; i < n; i++) c[x[i] = s[i]]++;  
  35.     for(i = 1; i < m; i++) c[i] += c[i-1];  
  36.     for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;  
  37.   
  38. #ifdef DBG  
  39.     printf("sa Get:[");  
  40.     debug(sa);  
  41.     puts("");  
  42. #endif  
  43.   
  44.     for(int k = 1, p; k <= n; k<<=1, m=p) {  
  45.         p = 0;  
  46.         //y[]的下标就是对应的第二关键字排名，它是由sa[]直接得来的  
  47.         //另外y[]的内容就是第一关键字所在位置  
  48.         for(i = n-k; i < n; i++) y[p++] = i;  
  49.         for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;  
  50.   
  51. #ifdef DBG  
  52.         printf("Gain y:[");  
  53.         debug(y);  
  54.         printf("Look x:{");  
  55.         printf("%3d", x[0]);  
  56.         for(i = 1; i < n; i++) {  
  57.             printf(" %3d", x[i]);  
  58.         }puts("}");  
  59. #endif  
  60.   
  61.         //x[]的内容就是对应的第一关键字排名  
  62.         //根据x[]的内容和y[]的下标进行合并，得到新的排名作为sa[]的下标  
  63.         for(i = 0; i < m; i++) c[i] = 0;  
  64.         for(i = 0; i < n; i++) c[x[y[i]]]++;  
  65.         for(i = 1; i < m; i++) c[i] += c[i-1];  
  66.         for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];  
  67.   
  68. #ifdef DBG  
  69.         printf("sa Get:[");  
  70.         debug(sa);  
  71.         puts("");  
  72. #endif  
  73.   
  74.         //按照sa[]的顺序提取出老的x[]，计算新的x[]  
  75.         swap(x, y);  
  76.         p = 1; x[sa[0]] = 0;//sa[0]一定是添加的字符0，排名万年第0  
  77.         for(i = 1; i < n; i++) {  
  78.             x[sa[i]] = cmp(y, i, k) ? p-1 : p++;  
  79.         }  
  80.         //剪枝，此时x[]中已经没有相同的值，sa[]被确定  
  81.         if(p >= n) break;  
  82.     }  
  83. }  
  84.   
  85. void get_high()  
  86. {  
  87.     int k = 0;  
  88.     for(int i = 0; i < n; i++) rank[sa[i]] = i;  
  89.     for(int i = 0; i < n; i++) {  
  90.         if(k) k--;  
  91.         int j = sa[rank[i]-1];  
  92.         while(s[i+k] == s[j+k]) k++;  
  93.         high[rank[i]] = k;  
  94.     }  
  95. }  
  96.   
  97. void PR()  
  98. {  
  99.     printf("The rank is:\n");  
  100.     printf("%d", rank[0]);  
  101.     for(int i = 1; i < n-1; i++) printf(" %d", rank[i]);  
  102.     puts("");  
  103. }  
  104.   
  105. int main()  
  106. {  
  107.     scanf("%s", s);  
  108.     n = strlen(s) + 1;  
  109.     int maxi = 0;  
  110.     for(int i = 0; i < n; i++) {  
  111.         maxi = maxi > s[i] ? maxi : s[i];  
  112.     }  
  113.     s[n-1] = 0;  
  114.     build(maxi+1);  
  115.     get_high();  
  116. #ifdef DBG  
  117.     PR();  
  118. #endif  
  119.     return 0;  
  120. }  

根据这份代码，输入一些数据测试一下，仔细研究研究中间输出。

建议数据：

abaab

aabaaaab

banana

接下来是手跑过程：


方框代表里面的值是下标，花括号代表是数值。它们都是和第一行红色数字一一对应的。

我们暂时不去管第一关键字是怎样计算出来的。

根据上面的程序，自己来填写这张图当中的数值。一个一个填写就可以明白了。（x[ ]数组的值就直接看图上的，并且注意每一个x[ ]数组都是在上一层基数排序计算出来的）

sa[ ]的初始值恰好是根据字符出现次数一个一个来的，轻易就可以手跑出来。这就完成了一位数的基数排序。

蓝色的字是第二关键字，正好是从sa[ ]当中提取出来的。黄色的箭头表示没有第二关键字，它们的排名是自左向右从0开始填的，要先填完这个再提取其他的第二关键字。再次强调，虽然有线，但是第一关键字并不是sa[ ]数组当中的数！

然后给出的x[ ]和刚填完的y[ ]合并（绿色字体），计算出sa[ ]。这是两位数的基数排序。

接下来继续倍增，完成四位数的基数排序。（如果你困惑为什么还是只有两个数被线指着，建议阅读论文）

最后，其实本来是不用对八位数进行基数排序，因为这个时候新的x[ ]数组（图中倒数第二行）里面已经没有重复的排名了，而第一关键字是首要的，因此sa[ ]数组被确定下来了。这里可以加个剪枝，break一下。

怎样得到x[ ]数组：

在每一次得到sa[ ]数组之后，计算新的x[ ]，方法是按照sa[ ]当中的排名顺序，（即sa[1...n]）提取出旧的x[ ]（注意此时它的名字叫做y[ ]了）来计算。如果某字串跟之前的那个完全一样（即cmp()函数），排名就一样（p-1）。

根据上面的话，再来自己填写x[ ]数组吧！