ural1517

题解：

后缀数组

求一下最长公共字串

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

char s1[N],m,n,s2[N],ss[N];

int height[N],str[N],sa[N],Log[N],best[][N],rank[N],c[N],t1[N],t2[N];

void da(int *str,int n,int m)

{

    int *x=t1,*y=t2;

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

    for (int i=;i<n;i++)c[x[i]=str[i]]++;

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

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

    for (int k=;k<=n;k<<=)

     {

        int p=;

        for (int i=n-k;i<n;i++)y[p++]=i;

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

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

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

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

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

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

        swap(x,y);

        p=;x[sa[]]=;

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

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

        if (p>=n)break;

        m=p;

     }

}

void calheight(int *str,int n)

{

    int j,k=;

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

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

     {

        if (k)k--;

        j=sa[rank[i]-];

        while (str[i+k]==str[j+k])k++;

        height[rank[i]]=k;

     }

}

void init(int n)

{

    Log[]=-;

    for (int i=;i<=n;i++)Log[i]=(i&(i-))?Log[i-]:Log[i-]+;

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

    for (int i=;i<=Log[n];i++)

     for (int j=;j<=n;j++)best[i][j]=min(best[i-][j],best[i-][j+(<<(i-))]);

}

int lcp(int a,int b)

{

    a=rank[a];

    b=rank[b];

    if (a>b)swap(a,b);

    a++;

    int t=Log[b-a+];

    return min(best[t][a],best[t][b-(<<t)+]);

}

int main()

{

    while (~scanf("%d",&m))

     {

        scanf("%s%s",s1,s2);

        int l1=strlen(s1);

        int l2=strlen(s2);

        int len=;

        for (int i=;i<l1;i++)str[len++]=s1[i];

        str[len++]=;

        for (int i=;i<l2;i++)str[len++]=s2[i];

        str[len]=;

        da(str,len+,);

        calheight(str,len);

        int be,ans=;

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

         {

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

            if (ans<height[i])ans=height[i],be=sa[i];

         }

        for (int i=be;i<be+ans;i++)putchar(str[i]);

        puts("");

     }

    return ;

}