题面
给 (n) 个 (01) 串 (s_i)，(m) 个询问问 (s_{lsim r}) 的最长公共子串长度。
数据范围：(1le nle 20000)，(1le mle 10^5)，(sum |s_i|le 4cdot 10^5)。
蒟蒻语
蒟蒻看到这个题口胡了一个做法，然后轻松拿到了最优解，发现这是道大水题。
什么猫树或分治我没听说过，反正广义 SAM 上枚举子串乱搞 (Theta(nsqrt nlog n)) 跑得飞快。
蒟蒻解
首先把串建成广义 SAM 没有问题，为了方便我写了盗版的 /ch。
离线询问，把 ([l_i,r_i]) 这个询问挂到 (r_i) 上。
顺序枚举 (r)，同时干这些坏事：
把 (r_i=r) 的询问按 (l_i) 排序，设有 (qn) 个询问。
对于 SAM 的节点 (p)，维护 (li_p) 和 (ri_p)，表示 (s_{1sim r}) 中这个以这个节点为子串的最右连续区间。
维护方法是枚举 (s_r) 的所有子串（暴力跳每个前缀的 (fa)，时间复杂度 (Theta(nsqrt n))），通过 (r-1) 递推。
然后对于每个该串子串节点 (p)，lower_bound 找到第一个 (l_ige li_p)，对询问 ([i,qn]) 的答案都与该节点代表最长串长度取 (max)。
这东西根据单调性差分一下即可，然后就做完了。
代码
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
#define be(a) (a).begin()
#define en(a) (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)
#define L(i,a,b) for(int i=(b)-1,I=(a)-1;i>I;i--)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=2e4,lN=4e5,qN=1e5;
int n,qn,ans[qN];
string s[N];
vector<pair<int,int>> que[N];
//SuffixAutoMoton
const int tN=(lN<<1)+1,cN=2;
int tn,ch[tN][cN],fa[tN],len[tN];
int newsam(){
fill(ch[tn],ch[tn]+cN,-1),fa[tn]=-1;
return tn++;
}
int rt=newsam(),t;
void extend(int c){
int p=t,np=t=newsam();
len[np]=len[p]+1;
for(;~p&&!~ch[p][c];p=fa[p]) ch[p][c]=np;
if(!~p) fa[np]=rt;
else {
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else {
int nq=newsam();
copy(ch[q],ch[q]+cN,ch[nq]);
len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;
for(;~p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}
int li[tN],ri[tN],vis[tN];
//Main
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>qn;
R(i,0,n){
cin>>s[i],t=rt;
for(char c:s[i]) extend(c-'0');
}
R(i,0,qn){
int l,r; cin>>l>>r,--l,--r;
que[r].pb(mp(l,i));
}
fill(vis,vis+tn,-1);
fill(li,li+tn,-2),fill(ri,ri+tn,-2);
R(i,0,n){
sort(be(que[i]),en(que[i]));
vector<int> mx(sz(que[i])+1);
int p=rt,now=0;
for(char c:s[i]){
int q=p=ch[p][c-'0']; now++;
for(;~q&&vis[q]<i;q=fa[q]){
vis[q]=i;
if(ri[q]==i-1) ri[q]=i;
else li[q]=ri[q]=i;
int id=lower_bound(be(que[i]),en(que[i]),
mp(li[q],-1))-be(que[i]);
mx[id]=max(mx[id],min(len[q],now));
}
}
R(j,0,sz(que[i])) mx[j+1]=max(mx[j+1],mx[j]);
R(j,0,sz(que[i])) ans[que[i][j].y]=mx[j];
}
R(i,0,qn) cout<<ans[i]<<"
";
return 0;
}
祝大家学习愉快！