spoj220

题解：

后缀数组

把所有串连接起来

二分答案

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

const int N=;

typedef long long ll;

using namespace std;

char ch[N];

int str[N],l[N],mx[N],mn[N],in[N],k,wa[N],wb[N],wv[N],Ws[N],sa[N],Rank[N],height[N];

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

{

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

}

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

{

    int *x=wa,*y=wb;

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

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

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

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

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

     {

         p=;

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

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

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

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

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

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

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

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

        swap(x,y);p=;x[sa[]]=;

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

    }

}

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

{

    int j,k=;

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

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

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

}

int pd(int mid,int n)

{

    for (int i=;i<k;i++){mx[i]=;mn[i]=1e9;}

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

     {

        if (height[i]<mid)

         {

            for (int j=;j<k;j++)

             {

                mx[j]=;

                mn[j]=1e9;

             }

            mx[in[sa[i]]]=sa[i];

            mn[in[sa[i]]]=sa[i];

         }

        else

         {

            mx[in[sa[i]]]=max(mx[in[sa[i]]],sa[i]);

            mn[in[sa[i]]]=min(mn[in[sa[i]]],sa[i]);

            mx[in[sa[i-]]]=max(mx[in[sa[i-]]],sa[i-]);

            mn[in[sa[i-]]]=min(mn[in[sa[i-]]],sa[i-]);

            int j;

            for (j=;j<k;j++)

             if (mx[j]-mn[j]<mid)break;

            if (j==k) return ;

         }

     }

    return ;

}

int main()

{

    int cnt=,t;

    scanf("%d",&t);

    while (t--)

     {

        scanf("%d",&k);

        int n=;

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

         {

            scanf("%s",ch);

            l[i]=strlen(ch);

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

             {

                str[j]=ch[j-n]-'a'+;

                in[j]=i;

             }

            n+=l[i]+;

            str[n-]=+i;

         }

        n--;

        str[n]=;

        da(str,sa,n+,+k+);

        calheight(str,sa,n);

        int l=,r=;

        while (l<r)

         {

            int mid=(l+r+)/;

            if (pd(mid,n))l=mid;

            else r=mid-;

         }

        printf("%d\n",l);

     }

    return ;

}