4556: [Tjoi2016&Heoi2016]字符串
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 169 Solved: 87
[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
题解：
后缀数组
自己想了一个网上没有的方法。。。
首先，先用后缀数组搞出来 height[] 和 sa[] 。然后对于一组询问 s[a..b]的所有子串和s[c..d]的前缀 ，我们可以把 s[c..d] 在 后缀数组中的位置找到，也就是Rank[]。然后可以想到若 s[a..b]的子串 和 s[c..d] 的前缀相等，那么 对于一个s[a..b]的子串 所开头的后缀，一定和 s[c..d] 所开头的后缀 有公共前缀，也就是两串下标中间的部分的height[] 都是不为0的。
举例说明：
原串：ababa
询问：(a,b,c,d)=(3,4,1,5)
后缀排序后：
注意：sa[]全部＋1了，height[]为当前后缀和前一个后缀的公共前缀长度。
sa[] height[]
5 0 a
3 1 a b a
1 3 a b a b a
4 0 b a
2 2 b a b a
我们先找到s[c..d]串所开头的后缀：a b a b a
然后向前后扩展（这里只举例说明向前扩展）：
1. a b a b a 和 a b a 的前缀为3，而且sa[i-1]为3，所以可以向前扩展，长度更新为2（因为s[a..b]中a为3，b为4，所以不能更新为3，要不超出[a,b]范围了）。
2. a b a 和 a的前缀为1，但sa[i-1]为5，不在 [a,b] 也就是 [3,4] 范围中，所以开头既然不在就不用管了（但还要往前扩展）。
3. 到头了，没有前一个了，所以停止。
注意1：停止条件一个为到头了，还有一个为 height[i]<当前更新的最长长度 （因为可以想到向前和向后扩展的长度一直是单调不增的，所以可以很快就变为0）
注意2：每时每刻更新的最长长度都不能超出范围，也就是要小于 (d-c+1) 和 (b-sa[i]+1) ，sa[i]为当前扩展的串的开始位置。
注意3（最重要的一条）：因为向前扩展的途中，比如到了第i位，但是我们在这一位所用到的长度不一定是height[i]，而是从初始扩展的位置到第i位的 height[] 的最小值！！！就比如上方的样例， b a b a 和 a b a b a 的公共前缀不是3，也不是2，而是这两个串中间的最小的height[] ，也就是0。
向后扩展同理。
然后就没有了。。。
这样就可以跑得飞快，因为向前和向后扩展的次数不会太多。（字符全一样的就可以hack掉了QAQ,因为要扩展到开头和结尾）所以复杂度差不多就是 后缀数组的复杂度了 。。。
然后bzoj上排到第一啦。。。972ms。。。比第二名还快了4倍多呢。。。
正解见我下一篇博客。QAQ
自己对拍中发现的几组好数据：
in:
5 1
abaaa
4 5 1 4
out:
1
in:
9 1
baabbbbab
2 5 7 9
out:
1
in:
5 1
aaaab
2 3 4 5
out:
1
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
int Ws[MAXN],wa[MAXN],wb[MAXN],sa[MAXN],wv[MAXN],Rank[MAXN],height[MAXN];
char str[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');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=;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(j=,p=;p<n;j*=,m=p)
{
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<n;i++)wv[i]=x[y[i]];
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)Ws[wv[i]]++;
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
}
void calheight(int n)
{
int i,j,k=;
for(i=;i<=n;i++)Rank[sa[i]]=i;
for(i=;i<n;height[Rank[i++]]=k)
for(k?k--:,j=sa[Rank[i]-];str[i+k]==str[j+k];k++);
}
int Solve(int s1,int s2,int s3,int s4,int n)
{
int len=,wz,i,LEN=INF;
wz=Rank[s3-];//len=s4-s3+1;
if(sa[wz]>=s1&&sa[wz]<=s2)len=max(len,min(s4-s3+,s2-sa[wz]+));
for(i=wz;i>=;i--)
{
if(height[i]==||height[i]<=len)break;
if(sa[i-]>=s1&&sa[i-]<=s2)
{
len=max(len,min(min(min(LEN,height[i]),s2-sa[i-]+),s4-s3+));
//LEN=min(LEN,len);
}
LEN=min(LEN,height[i]);
}
LEN=INF;
for(i=wz+;i<=n;i++)
{
if(height[i]==||height[i]<=len)break;
if(sa[i]>=s1&&sa[i]<=s2)
{
len=max(len,min(min(min(LEN,height[i]),s2-sa[i]+),s4-s3+));
//LEN=min(LEN,len);
}
LEN=min(LEN,height[i]);
}
return len;
}
int main()
{
freopen("heoi2016_str.in","r",stdin);
freopen("heoi2016_str.out","w",stdout);
int n,m,lstr,i,s1,s2,s3,s4;
n=read();m=read();
scanf("\n%s",str);
lstr=strlen(str);
str[lstr+]=;
DA(str,sa,lstr+,);
calheight(lstr);
for(i=;i<=n;i++)sa[i]++;
for(i=;i<=m;i++)
{
s1=read();s2=read();s3=read();s4=read();
printf("%d\n",Solve(s1,s2,s3,s4,n));
}
fclose(stdin);
fclose(stdout);
return ;
}