![字符串[未AC]（后缀自动机）：HEOI 2016 str](https://image.shishitao.com:8440/aHR0cDovLzIxOC4yOC4xOS4yMjgvdXBsb2FkL2ltYWdlLzIwMTYwNDI0LzIwMTYwNDI0MjAxNjA1Xzg2MDcwLnBuZw%3D%3D.png?w=700&webp=1 "字符串[未AC]（后缀自动机）：HEOI 2016 str")
![字符串[未AC]（后缀自动机）：HEOI 2016 str](https://image.shishitao.com:8440/aHR0cDovLzIxOC4yOC4xOS4yMjgvdXBsb2FkL2ltYWdlLzIwMTYwNDI0LzIwMTYwNDI0MjAxNjE4XzY2NjIyLnBuZw%3D%3D.png?w=700&webp=1 "字符串[未AC]（后缀自动机）：HEOI 2016 str")
![字符串[未AC]（后缀自动机）：HEOI 2016 str](https://image.shishitao.com:8440/aHR0cDovLzIxOC4yOC4xOS4yMjgvdXBsb2FkL2ltYWdlLzIwMTYwNDI0LzIwMTYwNDI0MjAxNjI3XzcxMDMxLnBuZw%3D%3D.png?w=700&webp=1 "字符串[未AC]（后缀自动机）：HEOI 2016 str")
超级恶心，先后用set维护right，再用主席树维护，全部超时，本地测是AC的。放心，BZOJ上还是1S限制，貌似只有常数优化到一定境界的人才能AC吧。
总之我是精神胜利了哦耶QAQ
#include <iostream>
#include <cstring>
#include <cstdio>
#define lb lower_bound
#define ub upper_bound
#include <set>
using namespace std;
const int N=;
int fa[N][],ch[N][],len[N],pos[N];
int lst,cnt;set<int>t[N];
int n,Q,a,b,c,d;char s[N];
void Init(){lst=cnt=;}
void Insert(int c){
int p=lst,np=lst=++cnt;len[np]=len[p]+;
while(p&&ch[p][c]==)ch[p][c]=np,p=fa[p][];
if(!p)fa[np][]=;
else{
int q=ch[p][c],nq;
if(len[q]==len[p]+)fa[np][]=q;
else{
len[nq=++cnt]=len[p]+;
fa[nq][]=fa[q][];fa[q][]=fa[np][]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
while(ch[p][c]==q)ch[p][c]=nq,p=fa[p][];
}
}
}
int cntE,fir[N],to[N],nxt[N];
void addedge(int a,int b){
nxt[++cntE]=fir[a];
to[fir[a]=cntE]=b;
} set<int>Merge(set<int>x,set<int>y){
if(x.size()<y.size())swap(x,y);
x.insert(y.begin(),y.end());
//delete &y;
return x;
} void DFS(int x){
for(int i=fir[x];i;i=nxt[i])
DFS(to[i]),t[x]=Merge(t[x],t[to[i]]);
} bool Judge(int p,int l,int r){
return t[p].lb(l)!=t[p].ub(r);
} int Find(int x,int l){
for(int i=;i>=;i--)
if(fa[x][i]&&len[fa[x][i]]>=l)
x=fa[x][i];
return x;
} int Solve(){
int l=,r=min(d-c,b-a)+;
while(l<=r){
int mid=(l+r)>>;
int p=Find(pos[c],mid);
if(Judge(p,a,b-mid+))l=mid+;
else r=mid-;
}
return r;
} int main(){
freopen("heoi2016_str5.in","r",stdin);
freopen("heoi2016_str.out","w",stdout);
Init();scanf("%d%d%s",&n,&Q,s+);
for(int i=n;i>=;i--){Insert(s[i]-'a');t[pos[i]=lst].insert(i);}
for(int i=;i<=cnt;i++)addedge(fa[i][],i);DFS();
for(int k=;k<=;k++)
for(int i=;i<=cnt;i++)
fa[i][k]=fa[fa[i][k-]][k-];
while(Q --){
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",Solve());
}
return ;
}
然后是应该AC的：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
using namespace std;
const int N=;
int fa[N][],ch[N][],len[N],pos[N];
int lst,cnt,n,Q;char s[N];
void Init(){lst=cnt=;}
void Insert(int c){
int p=lst,np=lst=++cnt;len[np]=len[p]+;
while(p&&ch[p][c]==)ch[p][c]=np,p=fa[p][];
if(!p)fa[np][]=;
else{
int q=ch[p][c],nq;
if(len[q]==len[p]+)fa[np][]=q;
else{
len[nq=++cnt]=len[p]+;
fa[nq][]=fa[q][];fa[q][]=fa[np][]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
while(ch[p][c]==q)ch[p][c]=nq,p=fa[p][];
}
}
}
int cntE,fir[N],to[N],nxt[N];
void addedge(int a,int b){
nxt[++cntE]=fir[a];
to[fir[a]=cntE]=b;
} int id[N],ed[N],tot;
int rt[N],sum[N*],son[N*][];
void Insert(int pre,int &rt,int l,int r,int g){
sum[rt=++tot]=sum[pre]+;
son[rt][]=son[pre][];
son[rt][]=son[pre][];
if(l==r)return;int mid=l+r>>;
if(mid>=g)Insert(son[pre][],son[rt][],l,mid,g);
else Insert(son[pre][],son[rt][],mid+,r,g);
}
int Query(int x,int l,int r,int a,int b){
if(l>=a&&r<=b||!sum[x])return sum[x];
int ret=,mid=l+r>>;
if(mid>=a)ret=Query(son[x][],l,mid,a,b);
if(mid<b)ret+=Query(son[x][],mid+,r,a,b);
return ret;
} bool Judge(int p,int l,int r){
int A=Query(rt[l-],,cnt,id[p],ed[p]);
int B=Query(rt[r],,cnt,id[p],ed[p]);
return A<B;
} int st[N],top;
int main(){
freopen("heoi2016_str.in","r",stdin);
freopen("heoi2016_str.out","w",stdout);
Init();scanf("%d%d%s",&n,&Q,s+);
for(int i=n;i>=;i--)Insert(s[i]-'a'),pos[i]=lst;
for(int i=;i<=cnt;i++)addedge(fa[i][],i);
for(int k=;k<=;k++)for(int i=;i<=cnt;i++)
fa[i][k]=fa[fa[i][k-]][k-];
st[top=]=;
while(top){
int x=st[top];
if(id[x]){ed[x]=tot;top--;}
else{
id[x]=++tot;
for(int i=fir[x];i;i=nxt[i])
st[++top]=to[i];
}
} tot=;
for(int i=;i<=n;i++)
Insert(rt[i-],rt[i],,cnt,id[pos[i]]);
int a,b,c,d;
while(Q --){
scanf("%d%d%d%d",&a,&b,&c,&d);
int l=,r=min(d-c,b-a)+;
while(l<=r){
int mid=l+r>>,p=pos[c];
for(int i=;i>=;i--)
if(fa[p][i]&&len[fa[p][i]]>=mid)
p=fa[p][i];
if(Judge(p,a,b-mid+))l=mid+;
else r=mid-;
}
printf("%d\n",r);
}
//printf("%lf\n", (double)clock()/CLOCKS_PER_SEC);
return ;
}
有毒啊，后缀数组都写挂了，TLE。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=;
int n,Q,r[N],Wa[N],Wb[N],Wv[N],Ws[N];
int rk[N],sa[N],lcp[N],mm[N],Min[N][];
int len,cnt,ch[N*][],sum[N*],rt[N];
char s[N];
bool cmp(int *p,int i,int j,int l){
return p[i]==p[j]&&p[i+l]==p[j+l];
} void DA(int n,int m){
int i,j,p,*x=Wa,*y=Wb;
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)++Ws[x[i]=r[i]];
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[x[i]]]=i; for(p=,j=;p<n;m=p,j<<=){
for(p=,i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)++Ws[Wv[i]=x[y[i]]];
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[Wv[i]]]=y[i];
for(swap(x,y),x[sa[]]=,i=,p=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
} void LCP(int n){
int i,j,k=;
for(i=;i<=n;i++)rk[sa[i]]=i;
for(i=;i<n;lcp[rk[i++]]=k)
for(k-=k>,j=sa[rk[i]-];r[i+k]==r[j+k];k++);
} #define mid ((l+r)>>1)
void Insert(int pre,int &rt,int l,int r,int g,int d){
sum[rt=++cnt]=sum[pre]+d;ch[rt][]=ch[pre][];
ch[rt][]=ch[pre][];if(l==r)return;
if(mid>=g)Insert(ch[pre][],ch[rt][],l,mid,g,d);
else Insert(ch[pre][],ch[rt][],mid+,r,g,d);
} int Query(int pre,int rt,int l,int r,int a,int b){
if(l>=a&&r<=b)return sum[rt]-sum[pre];int ret=;
if(mid>=a)ret=Query(ch[pre][],ch[rt][],l,mid,a,b);
if(mid<b)ret+=Query(ch[pre][],ch[rt][],mid+,r,a,b);
return ret;
} void Prepare(int n){
mm[]=-;
for(int i=;i<=n;i++){
mm[i]=mm[i-];
if(!(i&i-))mm[i]+=;
Min[i][]=lcp[i];
}
for(int k=;k<=mm[n];k++)
for(int i=;i+(<<k-)<=n;i++)
Min[i][k]=min(Min[i][k-],Min[i+(<<k-)][k-]);
} int Qmin(int x,int y){
if(x>y)swap(x,y);x+=;int l=mm[y-x+];
return min(Min[x][l],Min[y-(<<l)+][l]);
} int a,b,c,d,lo,hi;
bool Check(int x,int n){
int l=,r=rk[c-]-,pl,pr;
while(l<=r){
if(Qmin(mid,rk[c-])>=x)r=mid-;
else l=mid+;
}pl=l;
l=rk[c-]+,r=n;
while(l<=r){
if(Qmin(rk[c-],mid)>=x)l=mid+;
else r=mid-;
}pr=r;
return Query(rt[pl-],rt[pr],,n,a,b-x+);
} int main(){
freopen("heoi2016_str.in","r",stdin);
freopen("heoi2016_str.out","w",stdout);
scanf("%d%d%s",&n,&Q,s);
for(;s[len];len++)r[len]=s[len];
DA(len+,);LCP(len);Prepare(len);
for(int i=;i<=len;i++)
Insert(rt[i-],rt[i],,len,sa[i]+,);
while(Q--){
scanf("%d%d%d%d",&a,&b,&c,&d);
lo=,hi=min(b-a+,d-c+);
while(lo<=hi){
int MID=(lo+hi)>>;
if(Check(MID,len))lo=MID+;
else hi=MID-;
}
printf("%d\n",hi);
}
return ;
}