hdu5442 Favorite Donut 后缀数组 长春网赛

wa从一点到晚上11点没停过，也不知道为什么错，第二天换了个思路做，终于过了。这题还是有点问题的，数据有点水，我看到有人贴的代码baabbaab这组数据是4 0，明显错的，但是却可以过。

下面的是我第一次写的代码，也不知道到底哪里错了，能想到的样例都过了。

正的直接后缀数组求出即可。反着的我还用height注意细节。

希望大牛们指出错误，我真的找了几个小时都找不出。

#include <stdio.h>

#include <string.h>

#define maxn 51000

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];

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

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

int min(int x,int y)

{return x<y?x:y;}

int max(int x,int y)

{return x>y?x:y;}

void da(int *r,int *sa,int n,int m)

{

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=;i<m;i++) ws[i]=;

    for(i=;i<n;i++) ws[x[i]=r[i]]++;

    for(i=;i<m;i++) ws[i]+=ws[i-];

    for(i=n-;i>=;i--) sa[--ws[x[i]]]=i;

    for(j=,p=;p<n;j*=,m=p)

    {

        for(p=,i=n-j;i<n;i++) y[p++]=i;

        for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

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

        for(i=;i<m;i++) ws[i]=;

        for(i=;i<n;i++) ws[wv[i]]++;

        for(i=;i<m;i++) ws[i]+=ws[i-];

        for(i=n-;i>=;i--) sa[--ws[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

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

    }

    return;

}

int Rank[maxn],height[maxn];

void calheight(int *r,int *sa,int n)

{

    int i,j,k=;

    for(i=;i<=n;i++) Rank[sa[i]]=i;

    for(i=;i<n;height[Rank[i++]]=k)

        for(k?k--:,j=sa[Rank[i]-];r[i+k]==r[j+k];k++);

    return;

}

int r[maxn],sa[maxn];

char s[maxn],st[maxn];

int main()

{

    int i,j,t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        if(n==)

        {

            printf("0 0\n");

            continue;

        }

        scanf("%s",s);

        int len=n;

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

            s[len++]=s[i];

        for(i=;i<len;i++)

            r[i]=s[i];

        r[len]=;

        da(r,sa,len+,);

        calheight(r,sa,len);

        int setone=;

        for(i=;i<=len;i++)

        {

            if(len-sa[i]-<n)

                continue;

            else if(height[i]>=n)

                setone=min(sa[i-],sa[i]);

            else

            {

                setone=sa[i];

            }

        }

        setone%=n;

        //printf("%d\n",setone);

        int fl=;

        for(i=len-;i>=;i--)

            st[fl++]=s[i];

        for(i=;i<len;i++)

            r[i]=st[i];

        r[len]=;

        da(r,sa,len+,);

        calheight(r,sa,len);

        int settwo=;

        for(i=;i<=len;i++)

        {

            if(len-sa[i]-<n)

                continue;

            else if(height[i]>=n)

                settwo=max(sa[i-],sa[i]);

            else

            {

                settwo=sa[i];

            }

        }

        //printf("%d\n",settwo);

        int flag=;

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

        {

            if(s[setone+i]==st[settwo+i])

                continue;

            else if(s[setone+i]>st[settwo+i])

            {

                flag=;

                break;

            }

            else

            {

                flag=;

                break;

            }

        }

        settwo=n-settwo%n-;

        if(flag==)

        {

            printf("%d 0\n",setone+);

        }

        else if(flag==)

        {

            printf("%d 1\n",settwo+);

        }

        else

        {

            if(settwo>=setone)

                printf("%d 0\n",setone+);

            else printf("%d 1\n",settwo+);

        }

    }

}

下面是ac代码，反向通过先在末尾加未出现过的最大字母，再多添加0（为了使0位附0），那么就能避免上面代码出现的情况，即满足条件的在sa[]里面的中间部分，但是不能确定后面是否还有，添加字母后，就能保证能够满足，这样只要在[0，原字符串长度）里找到最大的rank的位置就好。

#include <stdio.h>

#include <string.h>

#define maxn 101000

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];

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

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

int min(int x,int y)

{return x<y?x:y;}

int max(int x,int y)

{return x>y?x:y;}

void da(int *r,int *sa,int n,int m)

{

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=;i<m;i++) ws[i]=;

    for(i=;i<n;i++) ws[x[i]=r[i]]++;

    for(i=;i<m;i++) ws[i]+=ws[i-];

    for(i=n-;i>=;i--) sa[--ws[x[i]]]=i;

    for(j=,p=;p<n;j*=,m=p)

    {

        for(p=,i=n-j;i<n;i++) y[p++]=i;

        for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

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

        for(i=;i<m;i++) ws[i]=;

        for(i=;i<n;i++) ws[wv[i]]++;

        for(i=;i<m;i++) ws[i]+=ws[i-];

        for(i=n-;i>=;i--) sa[--ws[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

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

    }

    return;

}

int Rank[maxn],height[maxn];

void calheight(int *r,int *sa,int n)

{

    int i,j,k=;

    for(i=;i<=n;i++) Rank[sa[i]]=i;

    for(i=;i<n;height[Rank[i++]]=k)

        for(k?k--:,j=sa[Rank[i]-];r[i+k]==r[j+k];k++);

    return;

}

int r[maxn],sa[maxn];

char s[maxn],st[maxn];

int main()

{

    int i,j,t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        scanf("%s",s);

        memset(r,,sizeof(r));

        int len=n;

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

            s[len++]=s[i];

        for(i=;i<len;i++)

            r[i]=s[i];

        r[len]=;

        da(r,sa,len+,);

        calheight(r,sa,len);

        int setone=;

        int maxx=-;

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

        {

            if(maxx<Rank[i])

            {

                maxx=Rank[i];

                setone=i;

            }

        }

        //printf("%d\n",setone);

        memset(r,,sizeof(r));

        int fl=;

        for(i=len-;i>=;i--)

            st[fl++]=s[i];

        for(i=;i<len;i++)

            r[i]=st[i];

        r[len++]=;//添加一个最大的

        r[len]=;//0位无字符

        da(r,sa,len+,);

        calheight(r,sa,len);

        int settwo=;

        maxx=-;

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

        {

            if(maxx<Rank[i])

            {

                maxx=Rank[i];

                settwo=i;

            }

        }

        //printf("%d\n",settwo);

        int flag=;

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

        {

            if(s[setone+i]==st[settwo+i])

                continue;

            else if(s[setone+i]>st[settwo+i])

            {

                flag=;

                break;

            }

            else

            {

                flag=;

                break;

            }

        }

        settwo=n-settwo%n-;

        if(flag==)

        {

            printf("%d 0\n",setone+);

        }

        else if(flag==)

        {

            printf("%d 1\n",settwo+);

        }

        else

        {

            if(settwo>=setone)

                printf("%d 0\n",setone+);

            else printf("%d 1\n",settwo+);

        }

    }

    return ;

}