题面

题意

给出一个字符串，每次询问给出四个数a，b，c，d，求子串a~b的所有子串与子串c~d的最长LCP。

做法

首先可以发现答案有可二分性，因此可以先二分答案，这样问题就转化为了问左端点为a~（b-mid+1）的所有后缀中是否存在一个后缀与以c为左端点的后缀的LCP大于等于mid。
这个可以利用后缀数组来解决，首先二分求出与以c为左端点的后缀的LCP大于等于mid的后缀排名的范围，然后用主席树维护rank，就能判断一段区间内是否存在后缀排名在p~q之间的后缀。
总复杂度为O(n*(logn)^2)

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
#define N 100100
using namespace std;
int n,m,st[N],rnk[N],t[N],h[N],stb[N][20],lg[N],tmp,rt[N],tt=1,a,b,c,d;
char str[N];
struct Node
{
int ls,rs,sum;
}node[N*40];
inline bool cmp(int u,int v)
{
if(rnk[u]!=rnk[v]) return rnk[u]<rnk[v];
int nu,nv;
nu= u+tmp<=n?rnk[u+tmp]:-1;
nv= v+tmp<=n?rnk[v+tmp]:-1;
return nu<nv;
}
inline void get()
{
int i,j;
for(i=1;i<=n;i++)
{
stb[i][0]=h[i];
}
for(i=1;(1 << i)<=n;i++)
{
for(j=1;j+(1 << i)-1<=n;j++)
{
stb[j][i]=min(stb[j][i-1],stb[j+(1 << (i-1))][i-1]);
}
}
for(i=1,j=2;i<=n;i++)
{
lg[i]=lg[i-1];
if(i==j) lg[i]++,j<<=1;
}
}
inline int ask(int u,int v)
{
v--;
if(u>v) return n-st[u]+1;
int l=lg[v-u+1];
return min(stb[u][l],stb[v-(1 << l)+1][l]);
}
void build(int now,int l,int r)
{
if(l==r) return;
int mid=((l+r)>>1);
if(l<=mid)
{
node[now].ls=++tt;
build(tt,l,mid);
}
if(mid<r)
{
node[now].rs=++tt;
build(tt,mid+1,r);
}
}
void add(int now,int l,int r,int u)
{
node[now].sum++;
if(l==r) return;
int mid=((l+r)>>1);
if(u<=mid)
{
node[++tt]=node[node[now].ls];
node[now].ls=tt;
add(tt,l,mid,u);
}
else
{
node[++tt]=node[node[now].rs];
node[now].rs=tt;
add(tt,mid+1,r,u);
}
}
inline bool as(int zg,int yg,int l,int r,int u,int v)
{
if(l==u&&v==r) return node[yg].sum-node[zg].sum>0;
int mid=((l+r)>>1),res=0;
if(u<=mid)
{
res|=as(node[zg].ls,node[yg].ls,l,mid,u,min(v,mid));
}
if(mid<v)
{
res|=as(node[zg].rs,node[yg].rs,mid+1,r,max(u,mid+1),v);
}
return res;
}
inline bool judge(int u)
{
int i,j,l,r,mid,p,q;
for(l=1,r=rnk[c];l<r;)
{
mid=((l+r)>>1);
ask(mid,rnk[c])>=u?r=mid:l=mid+1;
}
p=l;
for(l=rnk[c]+1,r=n+1;l<r;)
{
mid=((l+r)>>1);
ask(rnk[c],mid)>=u?l=mid+1:r=mid;
}
q=l-1;
return as(rt[a-1],rt[b-u+1],0,n,p,q);
}
int main()
{
int i,j,l,r,mid;
cin>>n>>m;
scanf("%s",str+1);
for(i=1;i<=n;i++)
{
rnk[i]=str[i];
st[i]=i;
}
for(tmp=1;tmp<=n;tmp<<=1)
{
sort(st+1,st+n+1,cmp);
t[st[1]]=1;
for(i=2;i<=n;i++)
t[st[i]]=t[st[i-1]]+cmp(st[i-1],st[i]);
for(i=1;i<=n;i++) rnk[i]=t[i];
}
tmp=0;
for(i=1;i<=n;i++)
{
j=st[rnk[i]-1];
if(tmp) tmp--;
for(;i+tmp<=n&&j+tmp<=n&&str[i+tmp]==str[j+tmp];tmp++);
h[rnk[i]-1]=tmp;
}
get();
build(1,0,n);
rt[0]=1;
for(i=1;i<=n;i++)
{
rt[i]=++tt;
node[tt]=node[rt[i-1]];
add(tt,0,n,rnk[i]);
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
for(l=1,r=min(d-c+1,b-a+1)+1;l<r;)
{
mid=((l+r)>>1);
judge(mid)?l=mid+1:r=mid;
}
printf("%dn",l-1);
}
}

最后

以上就是冷酷小虾米为你收集整理的bzoj4556 [Tjoi2016&Heoi2016]字符串题面题意做法代码的全部内容，希望文章能够帮你解决bzoj4556 [Tjoi2016&Heoi2016]字符串题面题意做法代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。