bzoj 1640||1692: [Usaco2007 Dec]队列变换【后缀数组】

注意输出是80字符个一行！！

首先贪心很显然，就是两头尽量拿小的。

然后需要处理两头一样的情况，显然是选字典序小的一串，把数组反着接在原数组后面，然后跑sa，判断的时候直接比较rk数组

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=300005;

int n,sa[N],wa[N],wb[N],wv[N],wsu[N],rk[N];

char c[N],s[N],ch[10];

bool cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void saa(char *r,int n,int m)

{

    int *x=wa,*y=wb;

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

        wsu[i]=0;

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

        wsu[x[i]=r[i]]++;

    for(int i=1;i<m;i++)

        wsu[i]+=wsu[i-1];

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

        sa[--wsu[x[i]]]=i;

    for(int j=1,p=1;j<=n&&p<=n;j<<=1,m=p)

    {

        p=0;

        for(int i=n-j;i<n;i++)

            y[p++]=i;

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

            if(sa[i]>=j)

                y[p++]=sa[i]-j;

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

            wv[i]=x[y[i]];

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

            wsu[i]=0;

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

            wsu[wv[i]]++;

        for(int i=1;i<m;i++)

            wsu[i]+=wsu[i-1];

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

            sa[--wsu[wv[i]]]=y[i];

        swap(x,y);

        x[sa[0]]=0;

        p=1;

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

            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

    }

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

        rk[sa[i]]=i;

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%s",ch);

        c[n+n-i]=c[i]=ch[0];

    }

    c[n]='a'-1;

    saa(c,2*n+1,200);

    int l=0,r=n+1;

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

    {

        if(rk[l]<rk[r])

            putchar(c[l++]);

        else

            putchar(c[r++]);

        if(!((i+1)%80))

            putchar('\n');

    }

    return 0;

}

/*

6

A

C

D

B

C

B

*/

巴特西

bzoj 1640||1692: [Usaco2007 Dec]队列变换【后缀数组】

最新文章

热门文章