思路
和一个思路，改成多组数据就有三倍经验了
代码
#include#include #include using namespace std;int maxlen[202000],suflink[202000],barrel[202000],trans[202000][26],Nodecnt,ranks[202000];int New_state(int _maxlen,int *_trans,int _suflink){ ++Nodecnt; maxlen[Nodecnt]=_maxlen; if(_trans) for(int i=0;i<26;i++) trans[Nodecnt][i]=_trans[i]; suflink[Nodecnt]=_suflink; return Nodecnt;}int add_len(int u,int c){ int z=New_state(maxlen[u]+1,NULL,0); while(u&&trans[u][c]==0){ trans[u][c]=z; u=suflink[u]; } if(!u){ suflink[z]=1; return z; } int v=trans[u][c]; if(maxlen[v]==maxlen[u]+1){ suflink[z]=v; return z; } int y=New_state(maxlen[u]+1,trans[v],suflink[v]); suflink[v]=suflink[z]=y; while(u&&trans[u][c]==v){ trans[u][c]=y; u=suflink[u]; } return z;}void c_sort(int n,int lim){ memset(barrel,0,sizeof(barrel)); for(int i=1;i<=n;i++) barrel[maxlen[i]]++; for(int i=1;i<=lim;i++) barrel[i]+=barrel[i-1]; for(int i=1;i<=n;i++) ranks[barrel[maxlen[i]]--]=i; }int Ans[202000],mx[202000]; char s[202000];void init(void){ Nodecnt=1; memset(maxlen,0,sizeof(maxlen)); memset(trans,0,sizeof(trans)); memset(suflink,0,sizeof(suflink)); memset(ranks,0,sizeof(ranks)); memset(Ans,0,sizeof(Ans)); memset(mx,0,sizeof(mx));}int main(){ // freopen("test.in","r",stdin); int T; scanf("%d",&T); while(T--){ init(); int cnt=0,last=1,numx; Nodecnt=1; int len; scanf("%d",&numx); for(int i=1;i<=numx;i++){ scanf("%s",s+1); ++cnt; len=strlen(s+1); if(cnt==1){ for(int i=1;i<=len;i++) last=add_len(last,s[i]-'a'); c_sort(Nodecnt,200010); for(int i=1;i<=Nodecnt;i++) Ans[i]=maxlen[i]; } else{ memset(mx,0,sizeof(mx)); int nowp=1,lent=0; for(int i=1;i<=len;i++){ if(trans[nowp][s[i]-'a']){ lent++; nowp=trans[nowp][s[i]-'a']; } else{ while(nowp&&trans[nowp][s[i]-'a']==0) nowp=suflink[nowp]; if(!nowp){ nowp=1; lent=0; continue; } else{ lent=maxlen[nowp]+1; nowp=trans[nowp][s[i]-'a']; } } mx[nowp]=max(mx[nowp],lent); } for(int i=Nodecnt;i>=1;i--){ int t=ranks[i]; mx[suflink[t]]=max(mx[suflink[t]],mx[t]); } for(int i=1;i<=Nodecnt;i++) Ans[i]=min(Ans[i],mx[i]); } } int ans=0; for(int i=1;i<=Nodecnt;i++) ans=max(Ans[i],ans); printf("%d\n",ans); } return 0;}