后缀数组小结

一.必备学习资料

二. 模板及其注解：

//Rank[0~n-1]为有效值， Rank[n]必定为0是无效值。
//sa[1~n]为有效值，sa[0]必定为n是无效值。
//height[2~n]为有效值；height[1]为0。
bool cmp(int *r, int a, int b, int l)
{
    return r[a]==r[b] && r[a+l]==r[b+l];
}

int r[MAXN], sa[MAXN], Rank[MAXN], height[MAXN];
int t1[MAXN], t2[MAXN], c[MAXN];
void DA(int str[], int sa[], int Rank[], int height[], int n, int m)
{
    n++;    // 加多一位是为了在第一名之前插多一名，且为'',即字典序最小的，以便处理边界问题。
    int i, j, p, *x = t1, *y = t2;
    for(i = 0; i<m; i++) c[i] = 0;  //初始化每个“桶”
    for(i = 0; i<n; i++) c[x[i] = str[i]]++; //把每个数入桶
    for(i = 1; i<m; i++) c[i] += c[i-1];    // 求前缀和， 以便求出排名
    for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;  /*求出每个数的排名。这里从0开始枚举应该没问题， 
                                                  而下面那句必须从n-1来时枚举，详情看下面注释*/
    for(j = 1; j<=n; j <<= 1)
    {
        //x相当于Rank， y相当于sa
        //对第二关键字进行排序（借助上一次的第一关键字）：
        p = 0;
        for(i = n-j; i<n; i++) y[p++] = i;  //没有第二关键字的，第二关键字设为最小。这里从n-1开始枚举应该没问题。
        for(i = 0; i<n; i++) if(sa[i]>=j) y[p++] = sa[i]-j; //枚举sa数组，sa[i]-j的第二关键字为sa[i]
        //对第二关键字进行排序
        for(i = 0; i<m; i++) c[i] = 0;
        for(i = 0; i<n; i++) c[x[y[i]]]++;
        for(i = 1; i<m; i++) c[i] += c[i-1];
        for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i]; /*因为y的顺序是按照第二关键字的顺序来排的
                                                           第二关键字靠后的，在同一个第一关键字桶中排名越靠后*/

        //重新求x（即Rank），因为此时y没有作用，所以把x复制到y上，然后再根据y对x重新求值。
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for(i = 1; i<n; i++)
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j)?p-1:p++;
        if(p>=n) break; //关键字会越来越多，当大于等于n个时，即表明所有位置的排名都已明确，则排序结束。
        m = p;
    }

    int k = 0;
    n--;
    for(i = 0; i<=n; i++) Rank[sa[i]] = i;  //注:sa[0]必定为n， 因而避免了sa[Rank[i]-1]溢出。
    for(i = 0; i<n; i++)  //sa[0]必定为n， 即Rank[n]必定为0，所以只枚举到n-1，避免了sa[Rank[i]-1]溢出。
    {
        /*
            i与sa[Rank[i]-1]的最长前缀为height[Rank[i]]],
            那么i与sa[Rank[i]-1]都去掉第一个字符，就得到 i+1与sa[Rank[i]-1]+1，
            而i+1与sa[Rank[i]-1]+1的最长前缀显然为height[Rank[i]]-1.
            所以 height[Rank[i+1]] >= height[Rank[i]]-1。因而可以根据这个性质加快速度。
        */
        if(k) k--;
        j = sa[Rank[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[Rank[i]] = k;
    }
}