URAL 1517 Freedom of Choice(后缀数组，最长公共字串)

题目

输出最长公共字串

#define maxn 200010

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];}//yuan lai zhi qian ba zhe li de l cuo dang cheng 1 le ...

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

    }

}

int rankk[maxn],height[maxn];

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

{

    int i,j,k=;

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

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

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

}

int RMQ[maxn];

int mm[maxn];

int best[][maxn];

void initRMQ(int n)

{

    int i,j,a,b;

    for(mm[]=-,i=;i<=n;i++)

        mm[i]=((i&(i-))==) ? mm[i-]+:mm[i-];

    for(i=;i<=n;i++)best[][i]=i;

    for(i=;i<=mm[n];i++)

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

        {

            a=best[i-][j];

            b=best[i-][j+(<<(i-))];

            if(RMQ[a]<RMQ[b])best[i][j]=a;

            else best[i][j]=b;

        }

}

int askRMQ(int a,int b)

{

    int t;

    t=mm[b-a+];b-=(<<t)-;

    a=best[t][a];b=best[t][b];

    return RMQ[a]<RMQ[b]? a:b;

}

int lcp(int a,int b)

{

    int t;

    a=rankk[a]; b=rankk[b];

    if(a>b) {t=a;a=b;b=t;}

    return (height[askRMQ(a+,b)]);

}

    char s[maxn];

    int r[maxn],sa[maxn];

int main()

{

    int t;

    while(scanf("%d",&t)!=EOF)

    {

        scanf("%s",s);

        int len1=strlen(s);

        s[len1]='';//yin wei bu ce ng chu xian ,suo yi bu yong dan xin ying xiang jie guo

        scanf("%s",s+len1+);

        int len2=strlen(s);

        for(int i=;i<len2;i++)r[i]=s[i];//r[i]biao shi pai de shi di ji

        r[len2]=;//ji shu pai xu shi de xu yao ,zui hou yi ge jia she wei zui xiao

        da(r,sa,len2+,);

        calheight(r,sa,len2);

        int ans=,be=-;

        //bian li height shu zu, cong di 2 ge kai shi (xia biao shi cong 1 kai shi de )

        for(int i=;i<=len2;i++)

        {

            if(height[i]>ans)

            {

                if((len1<sa[i]&&len1>sa[i-])||(len1>sa[i]&&len1<sa[i-]))

                {

                    ans=height[i];be=sa[i];

                }

            }

        }

        if(be!=-)

            for(int i=be;i<be+ans;i++)printf("%c",s[i]);

        printf("\n");

    }

    return ;

}