bzoj 4556 字符串

时间：2021-03-29 16:37:33

后缀数组，暴力硬跑
贼快

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define MAXN 100005

 using namespace std;

 int buc[MAXN],wa[MAXN],wb[MAXN];

 int r[MAXN],sa[MAXN],rank[MAXN],height[MAXN];

 void getheight(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]-];r[i+k]==r[j+k];k++);

     return ;

 }

 bool cmp(int *c,int a,int b,int d)

     {return c[a]==c[b]&&c[a+d]==c[b+d];}

 void da(int n,int m=){

     int i,j,p,*x=wa,*y=wb,*t;

     for(i=;i<m;i++)buc[i]=;

     for(i=;i<n;i++)buc[x[i]=r[i]]++;

     for(i=;i<m;i++)buc[i]+=buc[i-];

     for(i=n-;~i;i--)sa[--buc[x[i]]]=i;

     for(j=,p=;p<n;j*=,m=p){

         for(i=n-j,p=;i<n;i++)y[p++]=i;

         for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

         for(i=;i<m;i++)buc[i]=;

         for(i=;i<n;i++)buc[x[y[i]]]++;

         for(i=;i<m;i++)buc[i]+=buc[i-];

         for(i=n-;~i;i--)sa[--buc[x[y[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++;

     }

     getheight(n);

     return ;

 }

 int n,q;

 char s[MAXN];

 int main(){

     scanf("%d%d",&n,&q);

     scanf("%s",s);

     for(int i=;i<n;i++)r[i]=s[i];

     da(n+);

     int ans,minn,pos,now,a,b,c,d;

     while(q--){

         scanf("%d%d%d%d",&a,&b,&c,&d);

         a--;b--;c--;d--;

         ans=; minn=min(d-c+,b-a+);

         pos=rank[c];

         if(sa[pos]>=a&&sa[pos]<=b)ans=max(ans,min(minn,min(b-sa[pos]+,d-c+)));

         minn=min(minn,height[pos]);

         for(int i=pos-;i>=;i--){

             if(minn<=ans)break;

             now=sa[i];

             if(now>=a&&now<=b)ans=max(ans,min(minn,min(b-sa[i]+,d-c+)));

             minn=min(minn,height[i]);

         }

         minn=min(d-c+,b-a+);

         for(int i=pos+;i<=n;i++){

             minn=min(minn,height[i]);

             if(minn<=ans)break;

             now=sa[i];

             if(now>=a&&now<=b){ans=max(ans,min(minn,min(b-sa[i]+,d-c+)));}

         }

         printf("%d\n",ans);

     }

     return ;

 }

相关文章