后缀数组学习笔记--后缀数组解题方法总结

http://hi.baidu.com/hell74111/blog/item/74bc6edc29429cd48d1029d5.html

我也是偶尔才看到后缀数组这个东西的，偶在数据结构面前就是个菜啊。

当时看后缀数组的介绍和代码的时候，真是痛不欲生，哎，智商真不行啊。下面的代码，我看了差不多一天的时间才看懂。真无语了。真不适合搞算法，也不 适合编程，MD现在却走在了这条路上。我把别人的代码稍加注释一下发上来吧，以让一些接触的朋友好理解一点，不至于像我怎么费力。ps：注释写的很搓，凑 合看吧。

代码是：后缀数组--字符串处理的有力工具 上面的。只是上面的解释，对我这种菜鸟，很费力，哎怨念啊。

#define MAXM 5100
#define MAXN 100000

int bucket[MAXM];//计数桶
int rankx[MAXN];
int ranky[MAXN];

//n标示r的长度，防止+l时，数组越界
bool cmp(int *r, int a, int b, int l, int n)
{
if (r[a]==r[b])
{
   if (a+l     return true;
   else
    return false;
}
else
   return false;
}
void Suffix_Array_Init(char *s, int *sa, int n, int m)
{
int i;
int j;
int p;

int *x = rankx;
int *y = ranky ;
int *t;
//第一次基数排，不理解用数组方式进行基数排序的话，可以稍微自己动手画画看看
for (i=0; i for (i=0; i for (i=1; i for (i=n-1; i>=0; i--) sa[--bucket[x[i]]] = i;

//倍增进行基数排序
//根据其两个关键字进行排序
//解释：这里p代表了不同的字符串的个数，如果p=n就说明，后缀数组已经形成了，即rank已经完成
//第一次排序完成后，rank的值不会超过p，因此令m=p；这个在
for (j=1, p=1; p {
   //先按第二个关键字进行排序
   //y[]保存排序的结果：从小到大存放后缀串的序号
   //注意，最后的j位，其实是没有第二关键字的，设其第二关键字均为0，故依次放在排序结果y[]的前j位
   //sa[]是上一轮的后缀数组，sa[i]表示排在第i位的后缀串的编号
   //本次遍历时，上一轮的sa[]中的后缀串是其第前j后缀串的第二关键字
   //顺序遍历sa[]，将这个串所属的后缀串的序号填入y[]中，即可以完成排序
   //sa[]>=j是因为，序号小于j的后缀串，肯定不属于任何后缀串的第二关键字
   for (p=0, i=n-j; i    for (i=0; i=j ) y[p++] = sa[i] - j;

   //在y[]的基础上对第一关键字进行排序,求出sa
   for (i=0; i    for (i=0; i    for (i=1; i    for (i=n-1; i>=0; i--) sa[--bucket[x[y[i]]]] = y[i];

   //由sa求出rank，即x；x保存每一轮的rank值
   //在由sa求rank时，由于可能存在关键字相同的后缀串，因此需要进行比较
   //根据前一轮的rank值，可以比较本次的后缀串是否相同
   t = x;x = y;y = t;

   //x[sa[0]]=0;然后遍历sa[]
   //排序根据sa[]顺序来进行
   for (i=1, x[sa[0]]=0 ,p=1; i    {
    x[sa[i]] = cmp(y, sa[i-1], sa[i], j, n)?p-1:p++;
   }
}
}