记录编号	482027	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2018-01-05 21:23:42	内存使用	0.81 MiB

#include <cstdio>
#include <cstring>
using namespace std;
#define L 2010
int n=1,ch[L<<1][27],maxn[L<<1],parent[L<<1],cnt[L<<1];
char s[L];
int root,last,sz;
inline int newnode(int len){maxn[++sz]=len;return sz;}
inline void intn(){sz=0;root=last=newnode(0);}
inline void insert(char c)
{
    int d=c-'a',p=last,np=newnode(maxn[p]+1),q,nq;
    for(;p&&!ch[p][d];p=parent[p])ch[p][d]=np;
    if(!p)parent[np]=root;
    else
    {
        q=ch[p][d];
        if(maxn[q]==maxn[p]+1)parent[np]=q;
        else
        {
            nq=newnode(maxn[p]+1),memcpy(ch[nq],ch[q],sizeof(ch[q]));
            parent[nq]=parent[q],parent[q]=parent[np]=nq;
            for(;p&&ch[p][d]==q;p=parent[p])ch[p][d]=nq;
        }
    }
    last=np;
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int Ans,len[L<<1],ans[L<<1],bin[L<<1],que[L<<1];
inline void match()
{
    scanf("%s",s+1),n=strlen(s+1);
    register int i,d,rt=root,tmp=0;
    memset(len,0,sizeof(len));
    for(i=1;i<=n;++i)
    {
        d=s[i]-'a';
        while(rt&&!ch[rt][d])rt=parent[rt];
        if(!rt)rt=root,tmp=0;
        else tmp=min(maxn[rt],tmp)+1,rt=ch[rt][d];
        len[rt]=max(len[rt],tmp);
    }
    for(i=sz;i;--i)len[parent[que[i]]]=max(len[parent[que[i]]],len[que[i]]);
    for(i=1;i<=sz;++i)ans[i]=min(ans[i],len[i]);
    //len[i]=0;
}
int main()
{
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
    //freopen("Ark.in","r",stdin);
    register int i,j,q,tmp;
    scanf("%d",&q);scanf("%s",s+1);intn();
    for(j=1,n=strlen(s+1);j<=n;++j)insert(s[j]);
    for(i=1;i<=sz;++i)ans[i]=maxn[i],++bin[maxn[i]];
    for(i=1;i<=sz;++i)bin[i]+=bin[i-1];
    for(i=sz;i;--i)que[bin[maxn[i]]--]=i;
    for(i=1;i<q;++i)match();
    for(i=1;i<=sz;++i)Ans=max(ans[i],Ans);
    printf("%d\n",Ans);
}