Boring counting

Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=3518

Mean:

给你一个字符串，求：至少出现了两次（无重叠）的子串的种类数。

analyse:

后缀数组中height数组的运用，一般这个数组用得很少。

总体思路：分组统计的思想：将相同前缀的后缀分在一个组，然后对于1到len/2的每一个固定长度进行统计ans。

首先我们先求一遍后缀数组，并把height数组求出来。height数组代表的含义是：字典序相邻(即rank数组相邻)的两个后缀的最长公共前缀的长度。

由于子串不能重叠，那么就可以确定出子串长度的取值范围：1~len/2。(维护sa[]的最大值和最小值是为了判断排名相邻两个字符串的距离是否大于k,只有大于k才能保证不重叠)。

接下来我们对1~len/2的每一个固定长度进行统计该长度的子串有多少种，一路累加即得答案。

关键是要理解使用height数组进行分组统计的过程。

Time complexity: O(nlogn)

Source code:

/** this code is made by crazyacking* Verdict: Accepted* Submission Date: 2015-05-09-21.22* Time: 0MS* Memory: 137KB*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define LL long long#define ULL unsigned long longusing namespace std;const int MAXN=1010;//以下为倍增算法求后缀数组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(const char *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
                      
                       =k) maxx=max(maxx,max(sa[i-1],sa[i])),minn=min(minn,min(sa[i-1],sa[i])); else { if(maxx-minn>=k) ans++; maxx=0,minn=INT_MAX; } } if(maxx-minn>=k)ans++; return ans;}int main(){ while(~scanf("%s",str) && strcmp(str,"#")!=0) { int len=strlen(str); /**< 传入参数：str,sa,len+1,ASCII_MAX+1 */ da(str,sa,len+1,130); /**< str,sa,len */ calheight(str,sa,len); LL ans=0; for(int i=1;i<=len/2;++i) ans+=solve(i,len); cout<
                       
                        <

View Code

转载于:https://www.cnblogs.com/crazyacking/p/4490844.html

你可能感兴趣的文章