任意选择一个串作为模式串，构建出后缀自动机。
然后用其他的串在后缀自动机上跑匹配。
然后就到了理解后缀自动机性质的时候。
在某一个节点的最大值是可以沿着parent树上传的。
然后用dp[i][j]表示字符串i在位置j上的匹配的最长长度。
然后上传即可。之后在每一个节点统计所有串的min，然后再取max即可。
写法很暴力，貌似已经接近n^2了，但是还是A掉了。
#include#include #include #include using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i<=k;--i)#define inf 0x3f3f3f3f#define ll long long#define maxn 5005 struct sam{ char s[maxn]; int dp[maxn][10],n; int last,cnt,len,lth; int go[maxn][26],l[maxn],fa[maxn]; void init() { last=cnt=1; memset(go,0,sizeof go); memset(dp,0,sizeof dp); } void add(int x) {// printf("add %d\n",x); int p=last,np=last=++cnt; l[np]=l[p]+1;// printf("on point %d\n",np); for (;p&&!go[p][x];p=fa[p]) go[p][x]=np; if (!p) fa[np]=1; else { int q=go[p][x]; if (l[q]==l[p]+1) fa[np]=q; else { int nq=++cnt; l[nq]=l[p]+1; memcpy(go[nq],go[q],sizeof go[q]); fa[nq]=fa[q]; fa[np]=fa[q]=nq; for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq; } } } void solve() { scanf("%d",&n); scanf("%s",s+1); lth=len=strlen(s+1); F(i,1,lth) add(s[i]-'a'); F(i,2,n) { scanf("%s",s+1); len=strlen(s+1); int now=1,t=0; F(j,1,len) { int x=s[j]-'a'; if (go[now][x]) {t++;now=go[now][x];} else { while (now&&!go[now][x]) now=fa[now]; if (!now) {t=0;now=1;} else t=l[now]+1,now=go[now][x]; } for (int k=now;k;k=fa[k]) dp[k][i]=max(dp[k][i],t); } } int ans=0; F(i,1,cnt) { int tmp=l[i]; F(j,2,n) tmp=min(tmp,dp[i][j]); ans=max(ans,tmp); } printf("%d\n",ans); }}SAM; int main(){ SAM.init(); SAM.solve();}