POI 2000 最长公共子串

SOL:以第一个串为模板建立后缀自动机，把后面几个串在SAM上跑一下。求max即可。

不会后缀自动机的同学点这里

#pragma optimize("-O2")
#include<bits/stdc++.h>
#define N 4003
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
struct S{
    int c[26],fa,val,now,min;
}T[N];
int tot=1,tmp,n,len,c[N],id[N],now,ti,x,last;
char ch[N];
inline int Sam(int x,int last){
    int np=++tot;
    T[np].val=T[last].val+1;
    for(;last&&(!T[last].c[x]);last=T[last].fa) T[last].c[x]=np;
    if (!last) T[np].fa=1;
    else {
        int q=T[last].c[x];
        if (T[last].val+1==T[q].val) T[np].fa=q;
        else {
            int nq=++tot;  T[nq]=T[q];
            T[nq].val=T[last].val+1;
            T[q].fa=T[np].fa=nq;
            for (;last&&T[last].c[x]==q;last=T[last].fa) T[last].c[x]=nq;
        }
    }
    return np;
}
int main () {
   freopen("pow.in","r",stdin);
   freopen("pow.out","w",stdout);
   scanf("%d",&n);
   scanf("%s",ch);
   len=strlen(ch);n--; last=1;
   for (int i=0;i<len;i++) 
     last=Sam(ch[i]-'a',last);
   for (int i=1;i<=tot;i++) c[T[i].val]++,T[i].min=T[i].val;
   for (int i=1;i<=len;i++) c[i]+=c[i-1];
   for (int i=tot;i;i--) id[c[T[i].val]--]=i;
   while (n--) {
          scanf("%s",ch);len=strlen(ch); now=1,ti=0;
          for (int i=0;i<len;i++) {
                  x=ch[i]-'a';
                 if (T[now].c[x]) now=T[now].c[x],ti++;
                 else {
                     while (now&&!T[now].c[x]) now=T[now].fa;
                     if (!now) ti=0,now=1;
                     else ti=T[now].val+1,now=T[now].c[x];
           }
           T[now].now=max(T[now].now,ti);
         }
       for (int i=tot;i ;i--) {
             tmp=id[i];
             T[tmp].min=min(T[tmp].min,T[tmp].now);
             if (T[tmp].fa) T[T[tmp].fa].now=max(T[tmp].now,T[T[tmp].fa].now);
             T[tmp].now=0;
       }
   }
   int ans=0;
   for (int i=1;i<=tot;i++) 
         ans=max(ans,T[i].min);
   printf("%d
",ans); return 0;
}