\(\color{white}{P5546 最长公共子串}\)
把字符串拼起来，也就是用 # 连接，然后在上面做最长重复且属于所有串的后缀均出现过的子串。也就是满足以下条件的子串
-
重复过
-
其中包含的后缀可以覆盖所有的串
这样的子串是合格的。要求求得一个最长的串满足上述条件。
最长也就是要求最大化 \(\min\{h[k]\} _{i < k \leq j}\) 而且要使第二个条件满足。
上面式子是单调不升的，所以最小化 \(j-i\) ，显然这是可以通过 two-pointer 维护的，而 2. 条件可以用类似莫队或者用前缀和维护，至于查询 \(\min\) ，滑动窗口、线段树、st 均可。这里选用线段树。因为很好写。
然后直接算就行了。
复杂度看似十分玄学，实际上瓶颈还是在于前面求 \(h\) 数组的 \(\mathcal{O(nlog^2n)}\)，写出来就可以 \(ac.\) 主要要注意上面的 \(<\) 符号，很容易被阴。
$\text{code}$
// Qx 's data
#include <bits/stdc++.h>
#define ll long long
using std::cin;
using std::cout;
using std::cerr;
const int N=20005,Time=10,inf=0x3f3f3f3f;
int T,n,w;
char ch[N*5];
int ed[Time+5];
int rk[N*10],sa[N*10],rk0[N*10];
int h[N*5];
char s[10][N];
int col[N*10],vis[N*10];
inline int gf(int x){
return vis[x];
}
inline void _sa(void){
for(int i=1;i<=n;++i)
rk[i]=ch[i],sa[i]=i;
for(w=1;w<=n;w<<=1){
std::stable_sort(sa+1,sa+n+1,[](int x,int y){
return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
});
int cnt=0;
memcpy(rk0,rk,sizeof rk);
for(int i=1;i<=n;++i){
if(rk0[sa[i]]==rk0[sa[i-1]] &&
rk0[sa[i]+w]==rk0[sa[i-1]+w])
rk[sa[i]]=cnt;
else
rk[sa[i]]=++cnt;
}
}
}
inline void _h(void){
int k=0;
for(int i=1;i<=n;++i)
rk[sa[i]]=i;
for(int i=1;i<=n;++i){
if(k) --k;
int j=sa[rk[i]-1];
while(ch[i+k]==ch[j+k] && ch[i+k]!='#') ++k;
h[rk[i]]=k;
}
return;
}
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
struct segtree{
int tree[N*40];
inline void pushup(int rt,int l=0,int r=0){
return tree[rt]=std::min(tree[ls],tree[rs]),void();
}
int query(int rt,int l,int r,int L,int R){
if(L<=l && r<=R) return tree[rt];
int res=inf;
if(L<=mid) res=std::min(res,query(lson,L,R));
if(R> mid) res=std::min(res,query(rson,L,R));
return res;
}
void Build(int rt,int l,int r){
if(l==r) return tree[rt]=h[l],void();
Build(lson) , Build(rson);
return pushup(rt,l,r),void();
}
}G;
int l=0,r=0,cs=0,ans=-inf;
inline void add(int x){
if(!x) return;
++col[x];
if(col[x]==1) ++cs;
}
inline void del(int x){
if(!x) return;
--col[x];
if(col[x]==0) --cs;
}
inline void buildvis(void){
for(int i=1;i<=T;++i){
for(int j=ed[i-1]+1;j<ed[i];++j)
vis[rk[j]]=i;
}
}
inline void two_pointer(void){
_sa(),_h();
G.Build(1,1,n);
buildvis();
l=r=1;
add(gf(1));
while(r<=n){
if(cs==T){
while(cs==T)del(gf(l)),++l;
--l,add(gf(l));
ans=std::max(ans,G.query(1,1,n,l+1,r));
}
++r;
add(gf(r));
}
printf("%d\n",ans);
}
int main(){
cin>>T;
for(int i=1;i<=T;++i) cin>>(s[i]+1);
for(int i=1;i<=T;++i) ed[i]=ed[i-1]+strlen(s[i]+1)+1;
for(int i=1;i<=T;++i){
int len=strlen(s[i]+1);
for(int j=1;j<=len;++j)
ch[++n]=s[i][j];
ch[++n]='#';
}
--n;
two_pointer();
}