题目
题目描述
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？
输入输出格式
输入格式：
输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。
输出格式：
对于每一次询问，输出答案。
输入输出样例
输入样例#1：
5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4
输出样例#1：
1
1
2
2
2
说明
对于10%的数据，1<=n,m<=3,00,
对于40%的数据，1<=n,m<=3,000,字符串中仅有a,b
对于100%的数据，1<=n,m<=100,000,字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n
题解
发现这样一个性质：
如果长度$x$是一个公共前缀，那么长度$x’$也是一个公共前缀
所以可以二分答案了，这样问题就转化成了求是否存在长度为$x$的公共前缀
$SA$做法：
因为$c$的位置已经给定了，所以可以求出来与后缀$[c,n]$的$lcp\ge x$的$rank$区间$[L,R]$，这个可以二分求定
现在就需要检验$[a,b-x+1]$中是否存在$rank_i$在$[L,R]$内，对字符串建立$rank$为值域的主席树，每次区间查询即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
using namespace std;
const int MAX=1e5+5;
struct p{
int x,l,r;
}s[MAX<<5];
int n,m,tot,M;
int tax[MAX],sa[MAX],rk[MAX],het[MAX],h[MAX],Log[MAX],rt[MAX];
int f[21][MAX];
char a[MAX];
bool cmp(int *a,int x,int y,int w) {return a[x]==a[y]&&a[x+w]==a[y+w];}
void rsort()
{
for(int i=0;i<=m;++i)
tax[i]=0;
for(int i=1;i<=n;++i)
++tax[rk[h[i]]];
for(int i=1;i<=m;++i)
tax[i]+=tax[i-1];
for(int i=n;i>=1;--i)
sa[tax[rk[h[i]]]--]=h[i];
}
void Suffix()
{
for(int i=1;i<=n;++i)
rk[i]=a[i],h[i]=i;
m=127,rsort();
for(int p=1,w=1,i;p<n;w+=w,m=p)
{
for(p=0,i=n-w+1;i<=n;++i)
h[++p]=i;
for(i=1;i<=n;++i)
if(sa[i]>w) h[++p]=sa[i]-w;
rsort(),swap(rk,h),rk[sa[1]]=p=1;
for(i=2;i<=n;++i)
rk[sa[i]]=cmp(h,sa[i],sa[i-1],w)?p:++p;
}
int j,k=0;
for(int i=1;i<=n;het[rk[i++]]=k)
for(k=k?k-1:k,j=sa[rk[i]-1];a[j+k]==a[i+k];++k);
}
int change(int pre,int l,int r,int x)
{
int k=++tot;
s[k]=s[pre],++s[k].x;
if(l==r) return k;
if(x<=mid) tl=change(s[pre].l,l,mid,x);
else tr=change(s[pre].r,mid+1,r,x);
return k;
}
int ask(int l,int r,int pre,int k,int L,int R)
{
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return s[k].x-s[pre].x;
return ask(l,mid,s[pre].l,tl,L,R)+ask(mid+1,r,s[pre].r,tr,L,R);
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void Init()
{
Log[0]=-1;
for(int i=1;i<=n;++i)
Log[i]=Log[i>>1]+1,f[0][i]=het[i],rt[i]=change(rt[i-1],1,n,rk[i]);
for(int i=1;i<=20;++i)
for(int j=1;j<=n;++j)
f[i][j]=min(f[i-1][j],f[i-1][min(n,j+(1<<(i-1)))]);
}
int GET_LCP(int l,int r)
{
if(l==r) return n-sa[l]+1;
int t=Log[r-l];
return min(f[t][l+1],f[t][r-(1<<t)+1]);
}
bool look(int L,int a,int b,int c)
{
int l=c,r=n,ans=c,_L,_R;
while(l<=r)
{
if(GET_LCP(c,mid)>=L) ans=mid,l=mid+1;
else r=mid-1;
}
_R=ans,l=1,r=ans=c;
while(l<=r)
{
if(GET_LCP(mid,c)>=L) ans=mid,r=mid-1;
else l=mid+1;
}
_L=ans;
return ask(1,n,rt[a-1],rt[b-L+1],_L,_R);
}
int main()
{
n=read(),M=read(),scanf("%s",a+1);
Suffix(),Init();
for(int i=1,a,b,c,d,l,r,ans;i<=M;++i)
{
a=read(),b=read(),c=read(),d=read(),l=1,ans=0,r=min(b-a+1,d-c+1);
while(l<=r)
{
if(look(mid,a,b,rk[c])) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
$SAM$做法：
同样是二分答案$mid$，令$pos=c+mid$，只需要找$right$集合中有$pos$的状态ta的$len$是否大于等于$mid$并且在区间$[a,b]$内
记录每个位置在$SAM$上对应的节点，倍增查找第一个$len$大于等于$mid$的节点，线段树合并判断$right$集合内是否有位置在区间$[a,b]$里就行了
$luogu$开$O2$会TLE……不知道为什么QAQ
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
int l,r;
}s[MAX<<5];
int n,m,tot;
int rt[MAX];
char a[MAX];
void change(int l,int r,int &k,int x)
{
if(!k) k=++tot;
if(l==r) return;
if(x<=mid) change(l,mid,tl,x);
else change(mid+1,r,tr,x);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int k=++tot;
return tl=merge(s[x].l,s[y].l),tr=merge(s[x].r,s[y].r),k;
}
bool ask(int l,int r,int k,int L,int R)
{
if(R<l||r<L||!k) return 0;
if(l>=L&&r<=R) return 1;
if(ask(l,mid,tl,L,R)) return 1;
return ask(mid+1,r,tr,L,R);
}
struct SAM{
int l,r,L;
int len[MAX],fa[MAX],tax[MAX],id[MAX],pos[MAX];
int son[MAX][26],f[19][MAX];
SAM() {l=r=1;}
void ins(int x,int id)
{
int tt=r;
len[r=++l]=++L,change(1,n,rt[r],id),pos[id]=r;
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[r]=fa[qwq]=l;
for(int i=0;i<26;++i)
son[l][i]=son[qwq][i];
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void Init()
{
for(int i=1;i<=l;++i)
++tax[len[i]],f[0][i]=fa[i];
for(int i=1;i<=18;++i)
for(int j=1;j<=l;++j)
f[i][j]=f[i-1][f[i-1][j]];
for(int i=1;i<=n;++i)
tax[i]+=tax[i-1];
for(int i=l;i>=1;--i)
id[tax[len[i]]--]=i;
for(int i=l;i>=1;--i)
if(fa[id[i]]) rt[fa[id[i]]]=merge(rt[fa[id[i]]],rt[id[i]]);
}
bool look(int A,int B,int c,int __L)
{
int d=c+__L-1,x=pos[d];
if(len[x]<__L) return 0;
for(int i=18;i>=0;--i)
if(len[f[i][x]]>=__L) x=f[i][x];
return ask(1,n,rt[x],A+__L-1,B);
}
}_S;
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),m=read(),scanf("%s",a+1);
for(int i=1;i<=n;++i)
_S.ins(a[i]-'a',i);
_S.Init();
for(int i=1,a,b,c,d,l,r,ans;i<=m;++i)
{
a=read(),b=read(),c=read(),d=read(),l=1,r=d-c+1,ans=0;
while(l<=r)
{
if(_S.look(a,b,c,mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
