HDU 5769 Substring-白红宇

HDU 5769 Substring

阅读量：6305 次

发布时间：2019-06-22

本文共 1877 字，大约阅读时间需要 6 分钟。

后缀数组。

然后按照排序完成之后的顺序，每个后缀统计贡献量。

统计第i个后缀的贡献的时候，如果这个后缀中没有X，贡献度为0。

有贡献的分3种情况考虑：

1.如果这个后缀height部分等于0（即与前一个后缀没有公共前缀），那么在height之后的部分中找到第一个X的位置pos，n-pos为贡献度。

2.如果这个后缀height部分不等于0，如果这个后缀的height部分有X，那么贡献度为n-SA[i]-height[i];

3.如果这个后缀height部分不等于0，如果这个后缀的height部分没有X，那么需要在height之后的部分中找到第一个X的位置pos，n-pos为贡献度。

寻找pos的话，可以预处理前缀X个数sum[i]，然后二分一下。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}inline int read(){ char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x;}const int maxn=100000+10;int wa[maxn],wb[maxn],wv[maxn],WS[maxn];int cmp(int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l];}void da(int *r,int *sa,int n,int m){ int i,j,p,*x=wa,*y=wb,*t; for(i=0; i
               
                =0; i--) sa[--WS[x[i]]]=i; for(j=1,p=1; p
                
                 =j) y[p++]=sa[i]-j; for(i=0; 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
                  
                   1) r=mid-1; else if(sum[mid]-D==1) pos=mid,r=mid-1; else l=mid+1; } return pos;}int main(){ scanf("%d",&T); int cas=1; while(T--) { scanf("%s%s",op,str); n=strlen(str); for(int i=0;i
                   
                    =0) sum[i]=sum[i-1]; if(a[i]==int(op[0])) sum[i]++; } LL ans=0; for(int i=0;i<=n;i++) { int D; if(SA[i]-1<0) D=0; else D=sum[SA[i]-1]; if(sum[n]-D==0) continue; if(height[i]==0) ans=ans+n-Find(D,SA[i],n); else { if(sum[SA[i]+height[i]-1]-D!=0) ans=ans+n-SA[i]-height[i]; else ans=ans+n-Find(sum[SA[i]+height[i]-1],SA[i]+height[i],n); } } printf("Case #%d: %lld\n",cas++,ans); } return 0;}

转载于:https://www.cnblogs.com/zufezzt/p/5720983.html

你可能感兴趣的文章

张小龙2018PRO版微信公开课演讲全文透露2018微信全新计划