中文字幕在线观看,亚洲а∨天堂久久精品9966,亚洲成a人片在线观看你懂的,亚洲av成人片无码网站,亚洲国产精品无码久久久五月天

后綴數(shù)組之倍增算法

2018-07-20    來源:open-open

容器云強(qiáng)勢上線!快速搭建集群,上萬Linux鏡像隨意使用
#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;

    //其實(shí)下面的是計(jì)數(shù)排序

    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];//其實(shí)這個(gè)時(shí)候每個(gè)數(shù)的名次已經(jīng)有了

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

    /*最后一個(gè)for循環(huán)可能感覺莫名其妙可以改成下面兩個(gè)for循環(huán)可能就很容易的看出來了

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

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

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

        sa[rank[i]]=i;

    根據(jù)sa[rank[i]]=i這個(gè)定理把rank[i]為--c[x[x[i]]]所以把--c[x[x[i]]]帶入第二個(gè)

    for循環(huán)就化為了上面計(jì)數(shù)排序的最后一個(gè)for循環(huán)

    */

    for(int k=1;k<=n;k<<=1/*和k=k*2等價(jià)*/)

    {

        int p=0;

        /*直接利用sa數(shù)組排序第二關(guān)鍵字也就是相當(dāng)于一個(gè)兩位數(shù)的個(gè)位數(shù),y保存的是第二關(guān)鍵字

        的sa[i]的值

        */

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

            y[p++]=i;/*因?yàn)榈诙P(guān)鍵字超范圍,看做小于所有的第二關(guān)鍵字,所以他們的排名

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

            根據(jù)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;

        /*因?yàn)檫@是排的第二關(guān)鍵字,當(dāng)位于最后的后綴可能已經(jīng)沒有第二個(gè)已經(jīng)沒有第二個(gè)關(guān)鍵字了

          這個(gè)時(shí)候就把這樣的關(guān)鍵字都初始化為小于所有的第二關(guān)鍵字,而且,suffix(sa[0])<=suffix(sa[1])..

          當(dāng)我們排第二關(guān)鍵字的時(shí)候第一關(guān)鍵字已經(jīng)沒有用了,換句話說,前k個(gè)我們已經(jīng)用不到了,也就是

          下標(biāo)小于k的,也就是sa[i]小于k的,舉個(gè)例子baba這個(gè)字符串第一次算出來的sa數(shù)組為1 3 0 2,也就是

          suffix(1)<=suffix(3)<=suffix(0)<suffix(2)也就是a<=a<=b<=b而第二關(guān)鍵字為aba@這個(gè)@是小于所有的

          字符,而第一個(gè)a就沒有用了,也就是sa[k]=0的就沒有用了,因?yàn)閟a[k]表示的是以0首字符為下標(biāo)的

          的排名為k這個(gè)時(shí)候我們已經(jīng)不再需要排小于k的下標(biāo)了,但去掉小于k的sa[]后他們的sa[]的值是相對的

          如去掉0以后就剩下132了因?yàn)槿サ袅?個(gè)所以所有大于等于1的都得減1,同理,去掉k個(gè)就得減去k個(gè)

        */

        //基數(shù)排序第一個(gè)關(guān)鍵字x數(shù)組存的是相當(dāng)于rank[],且y[i]相當(dāng)于與第一關(guān)鍵字,可以手動(dòng)模擬一下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]看成一個(gè)下標(biāo)

        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];

        這個(gè)時(shí)候sa數(shù)組存的已經(jīng)是倍增后的值但是這個(gè)時(shí)候rank[sa[i]]=i還不一定成立所以需要在下面進(jìn)行驗(yàn)證

        */

        //根據(jù)sa和y數(shù)組計(jì)算新的x數(shù)組(這時(shí)說的y是x數(shù)組和y數(shù)組交換后的y數(shù)組也就相當(dāng)于rank數(shù)組)

        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長度的字符串內(nèi)肯定不包括@(這也是最后

        一個(gè)元素給@的原因),所以sa[i-1]+k,sa[i]+k都小于n-k,所以此處數(shù)組不會(huì)越界。若果不相等那么

        根據(jù)&&的短路特性后邊的sa[i]+k就不會(huì)判斷了

        */

    }

}

int main()

{

    return 0;

}

/*

dcba

aabb

baba

bababa

bbaa

aaab

*/

 

標(biāo)簽: swap 排名

版權(quán)申明:本站文章部分自網(wǎng)絡(luò),如有侵權(quán),請聯(lián)系:west999com@outlook.com
特別注意:本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)!
本站所提供的圖片等素材,版權(quán)歸原作者所有,如需使用,請與原作者聯(lián)系。

上一篇:PHP獲取時(shí)間段代碼

下一篇:jQuery計(jì)時(shí)器