后缀数组之倍增算法

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

#define MAXN   123123

char s[MAXN];

int sa[MAXN],t[MAXN],t2[MAXN],c[MAXN],n;

void build(int m)

{

    int i,*x=t,*y=t2;

    //其实下面的是计数排序

    for(i=0;i<m;i++) c[i]=0;

    for(i=0;i<n;i++) c[x[i]=s[i]]++;

    for(i=0;i<m;i++) c[i]+=c[i-1];//其实这个时候每个数的名次已经有了

    for(i=n-1;i>=0;i--)  sa[--c[x[i]]]=i;

    /*最后一个for循环可能感觉莫名其妙可以改成下面两个for循环可能就很容易的看出来了

    for(i=n-1;i>=0;i--)

        rank[i]=--c[x[x[i]]];

    for(i=n-1;i>=0;i--)

        sa[rank[i]]=i;

    根据sa[rank[i]]=i这个定理把rank[i]为--c[x[x[i]]]所以把--c[x[x[i]]]带入第二个

    for循环就化为了上面计数排序的最后一个for循环

    */

    for(int k=1;k<=n;k<<=1/*和k=k*2等价*/)

    {

        int p=0;

        /*直接利用sa数组排序第二关键字也就是相当于一个两位数的个位数，y保存的是第二关键字

        的sa[i]的值

        */

        for(i=n-k;i<n;i++)

            y[p++]=i;/*因为第二关键字超范围，看做小于所有的第二关键字，所以他们的排名

            rank[n-k]...rank[n-1]的排名为0,1,2,....所以y[rank[n-k]]...y[rank[n-1]]的值位n-k...n-1

            根据sa[rank[i]]=i;化简得rank[0]..rank[k]的值为n-k...n-1

        */

        for(i=0;i<n;i++)

            if(sa[i]>=k) y[p++]=sa[i]-k;

        /*因为这是排的第二关键字，当位于最后的后缀可能已经没有第二个已经没有第二个关键字了

          这个时候就把这样的关键字都初始化为小于所有的第二关键字，而且，suffix(sa[0])<=suffix(sa[1])..

          当我们排第二关键字的时候第一关键字已经没有用了，换句话说，前k个我们已经用不到了，也就是

          下标小于k的，也就是sa[i]小于k的，举个例子baba这个字符串第一次算出来的sa数组为1 3 0 2，也就是

          suffix(1)<=suffix(3)<=suffix(0)<suffix(2)也就是a<=a<=b<=b而第二关键字为aba@这个@是小于所有的

          字符，而第一个a就没有用了，也就是sa[k]=0的就没有用了，因为sa[k]表示的是以0首字符为下标的

          的排名为k这个时候我们已经不再需要排小于k的下标了，但去掉小于k的sa[]后他们的sa[]的值是相对的

          如去掉0以后就剩下132了因为去掉了1个所以所有大于等于1的都得减1，同理，去掉k个就得减去k个

        */

        //基数排序第一个关键字x数组存的是相当于rank[],且y[i]相当于与第一关键字，可以手动模拟一下baba

        for(i=0;i<m;i++) c[i]=0;

        for(i=0;i<n;i++) c[x[y[i]]]++;

        for(i=0;i<m;i++) c[i]+=c[i-1];

        for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];

        /*

        可以换成下面的for更直观一些rank1记录的是rank的值,把y[i]看成一个下标

        for(i=0;i<m;i++) 

            rank[i]=x[y[i]];

        for(i=0;i<n;i++) c[i]=0;

        for(i=0;i<m;i++)

            c[rank[i]]++;

        for(i=0;i<m;i++)  c[i]+=c[i-1];

        for(i=n-1;i>=0;i--)

            rank1[y[i]]==--c[x[y[i]]];

        for(i=n-1;i>=0;i--)

            sa[rank1[y[i]]]=y[i];

        把rank1=--c[x[y[i]]]带入得sa[--c[x[y[i]]]]=y[i];

        这个时候sa数组存的已经是倍增后的值但是这个时候rank[sa[i]]=i还不一定成立所以需要在下面进行验证

        */

        //根据sa和y数组计算新的x数组（这时说的y是x数组和y数组交换后的y数组也就相当于rank数组）

        swap(x,y);

        p=1;x[sa[0]]=0;

        for(i=1;i<n;i++)

            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;

        if(p>=n) break;

        m=p;

        /*

        如果r[sa[i-1]]==r[sa[i]],那么，说明在以a,b为开始的l长度的字符串内肯定不包括@（这也是最后

        一个元素给@的原因），所以sa[i-1]+k,sa[i]+k都小于n-k，所以此处数组不会越界。若果不相等那么

        根据&&的短路特性后边的sa[i]+k就不会判断了

        */

    }

}

int main()

{

    return 0;

}

/*

dcba

aabb

baba

bababa

bbaa

aaab

*/

 

标签： swap 排名

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。