4556: [Tjoi2016&Heoi2016]字符串

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 169  Solved: 87

[][][]

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

Sample Output

1

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

1 #include
      
        2 using namespace std; 3 #define MAXN 100010 4 #define INF 1e9 5 int Ws[MAXN],wa[MAXN],wb[MAXN],sa[MAXN],wv[MAXN],Rank[MAXN],height[MAXN]; 6 char str[MAXN]; 7 int read() 8 { 9     int s=0,fh=1;char ch=getchar();10     while(ch<'0'||ch>'9'){
    if(ch=='-')fh=-1;ch=getchar();}11     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}12     return s*fh;13 }14 int cmp(int *r,int a,int b,int l){
    return (r[a]==r[b])&&(r[a+l]==r[b+l]);}15 void DA(char *r,int *sa,int n,int m)16 {17     int i,j,p,*x=wa,*y=wb,*t;18     for(i=0;i
       
        =0;i--)sa[--Ws[x[i]]]=i;22     for(j=1,p=1;p
        
         =j)y[p++]=sa[i]-j;26         for(i=0;i
         
          =0;i--)sa[--Ws[wv[i]]]=y[i];31         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
          
           =s1&&sa[wz]<=s2)len=max(len,min(s4-s3+1,s2-sa[wz]+1));47     for(i=wz;i>=2;i--)48     {49         if(height[i]==0||height[i]<=len)break;50         if(sa[i-1]>=s1&&sa[i-1]<=s2)51         {52             len=max(len,min(min(min(LEN,height[i]),s2-sa[i-1]+1),s4-s3+1));53             //LEN=min(LEN,len);54         }55         LEN=min(LEN,height[i]);56     }57     LEN=INF;58     for(i=wz+1;i<=n;i++)59     {60         if(height[i]==0||height[i]<=len)break;61         if(sa[i]>=s1&&sa[i]<=s2)62         {63             len=max(len,min(min(min(LEN,height[i]),s2-sa[i]+1),s4-s3+1));64             //LEN=min(LEN,len);65         }66         LEN=min(LEN,height[i]);67     }68     return len;69 }70 int main()71 {72     freopen("heoi2016_str.in","r",stdin);73     freopen("heoi2016_str.out","w",stdout);74     int n,m,lstr,i,s1,s2,s3,s4;75     n=read();m=read();76     scanf("\n%s",str);77     lstr=strlen(str);78     str[lstr+1]=0;79     DA(str,sa,lstr+1,256);80     calheight(lstr);81     for(i=1;i<=n;i++)sa[i]++;82     for(i=1;i<=m;i++)83     {84         s1=read();s2=read();s3=read();s4=read();85         printf("%d\n",Solve(s1,s2,s3,s4,n));86     }87     fclose(stdin);88     fclose(stdout);89     return 0;90 }