4556: [Tjoi2016&Heoi2016]字符串
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 177 Solved: 92
[Submit][Status][Discuss]
Description
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了
一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CE
O，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公
共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？
Input
输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来
m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。1<=n,m<=100,000,
字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n
Output
对于每一次询问，输出答案。
Sample Input
5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4
Sample Output
1
1
2
2
2
1
2
2
2
HINT
Source
题解:
后缀数组+二分+主席树+ST表
先将原字符串的Rank[],sa[],height[]用后缀数组求出来。用ST表把height[]的区间最小值求出来。把Rank[]建到主席树上。
对于每一组询问(a,b,c,d)，先二分答案。然后去找到(c,d)串在后缀中的位置，并向前向后扩展，用ST表把和(c,d)串公共前缀长度大于mid的范围[L,R]找到。最后只需要在主席树上的root[s1~s2-mid+1]中找到Rank[]在范围[L,R]中的即可。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int root[MAXN],Ws[MAXN],wa[MAXN],wb[MAXN],sa[MAXN],wv[MAXN],Rank[MAXN],height[MAXN],MN[MAXN][17],sum[MAXN*18],ls[MAXN*18],rs[MAXN*18],SIZE;
char str[MAXN];
int read()
{
int s=0,fh=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
return s*fh;
}
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&&(r[a+l]==r[b+l]);}
void DA(char *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++)Ws[i]=0;
for(i=0;i<n;i++)Ws[x[i]=r[i]]++;
for(i=0;i<m;i++)Ws[i]+=Ws[i-1];
for(i=n-1;i>=0;i--)sa[--Ws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<n;i++)wv[i]=x[y[i]];
for(i=0;i<m;i++)Ws[i]=0;
for(i=0;i<n;i++)Ws[wv[i]]++;
for(i=0;i<m;i++)Ws[i]+=Ws[i-1];
for(i=n-1;i>=0;i--)sa[--Ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calheight(int n)
{
int i,j,k=0;
for(i=1;i<=n;i++)Rank[sa[i]]=i;
for(i=0;i<n;height[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1];str[i+k]==str[j+k];k++);
}
void ST(int n)
{
int i,j;
for(i=1;i<=n;i++)MN[i][0]=height[i];
for(j=1;(1<<j)<=n;j++)
{
for(i=1;i+(1<<j)-1<=n;i++)
{
MN[i][j]=min(MN[i][j-1],MN[i+(1<<(j-1))][j-1]);
}
}
}
void Insert(int x,int &y,int l,int r,int I)
{
y=++SIZE;
sum[y]=sum[x]+1;
if(l==r)return;
int mid=(l+r)/2;
ls[y]=ls[x];rs[y]=rs[x];
if(I<=mid)Insert(ls[x],ls[y],l,mid,I);
else Insert(rs[x],rs[y],mid+1,r,I);
}
int Query(int x,int y,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return sum[y]-sum[x];
int mid=(l+r)/2;
if(qr<=mid)return Query(ls[x],ls[y],l,mid,ql,qr);
else if(ql>mid)return Query(rs[x],rs[y],mid+1,r,ql,qr);
else return Query(ls[x],ls[y],l,mid,ql,mid)+Query(rs[x],rs[y],mid+1,r,mid+1,qr);
}
int main()
{
freopen("heoi2016_str.in","r",stdin);
freopen("heoi2016_str.out","w",stdout);
int n,m,lstr,i,s1,s2,s3,s4,wz,l,r,ans,j,mid,last,next,MID,wz1,wz2;
n=read();m=read();
scanf("\n%s",str);
lstr=strlen(str);
str[lstr+1]=0;
DA(str,sa,lstr+1,256);
calheight(lstr);
ST(lstr);
SIZE=0;
for(i=lstr;i>=1;i--)Rank[i]=Rank[i-1];
for(i=1;i<=n;i++)Insert(root[i-1],root[i],1,n,Rank[i]);
for(i=1;i<=m;i++)
{
s1=read();s2=read();s3=read();s4=read();
wz=Rank[s3];
l=1;r=min(s2-s1+1,s4-s3+1);ans=0;
while(l<=r)
{
mid=(l+r)/2;
wz1=wz2=wz;MID=mid;
for(j=16;j>=0;j--)if(wz1>=(1<<j)&&MN[wz1-(1<<j)+1][j]>=MID)wz1-=(1<<j);
for(j=16;j>=0;j--)if(wz2+(1<<j)<=n&&MN[wz2+1][j]>=MID)wz2+=(1<<j);
if(Query(root[s1-1],root[s2-mid+1],1,n,wz1,wz2)>0){ans=mid;l=mid+1;}
else r=mid-1;
}
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}