题目大意：求n个串的最长公共子串
太久没写SAM了真是……
将第一个串建成后缀自动机，用其它的串进去匹配
每个节点记录每个串在上面匹配的最大长度
那么这个节点对答案的贡献就是所有最大长度的最小值
对所有贡献取最大就行了= = 这最大最小看着真是别扭
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 10100using namespace std;int n,ans;char s[M];namespace Suffix_Automaton{struct SAM{SAM *parent,*son[26];int max_len,min_len[6];bool v;SAM(int _=0):parent(0x0),max_len(_),v(false){memset(son,0,sizeof son);memset(min_len,0,sizeof min_len);}}*root=new SAM,*last=root;void Extend(int x){SAM *p=last;SAM *np=new SAM(p->max_len+1);while(p&&!p->son[x])p->son[x]=np,p=p->parent;if(!p) np->parent=root;else{SAM *q=p->son[x];if(p->max_len+1==q->max_len)np->parent=q;else{SAM *nq=new SAM(p->max_len+1);nq->parent=q->parent;memcpy(nq->son,q->son,sizeof nq->son);q->parent=nq;np->parent=nq;for(;p&&p->son[x]==q;p=p->parent)p->son[x]=nq;nq->min_len[1]=nq->max_len;}}last=np;np->min_len[1]=np->max_len;}void DFS(SAM *p){int i,temp=0x3f3f3f3f;for(i=1;i<=n;i++)temp=min(temp,p->min_len[i]);ans=max(ans,temp);p->v=true;for(i=0;i<26;i++)if( p->son[i] && !p->son[i]->v )DFS(p->son[i]);}}int main(){using namespace Suffix_Automaton;int i,j;cin>>n;scanf("%s",s+1);for(i=1;s[i];i++)Extend(s[i]-'a');for(i=2;i<=n;i++){scanf("%s",s+1);SAM *p=root;int len=0;for(j=1;s[j];j++){while( p!=root && !p->son[s[j]-'a'] )p=p->parent,len=p->max_len;if( p->son[s[j]-'a'] )p=p->son[s[j]-'a'],len++;for(SAM* temp=p;temp;temp=temp->parent)temp->min_len[i]=max(temp->min_len[i],min(len,temp->max_len) );}}DFS(root);cout<<ans<<endl;}
，还有不愿面对失败的尴尬。曾经怀有远大理想，拥有完美的憧憬。
