hdu 5769后缀数组求含有某个字母的某个字符串的不同子串的个数-白红宇

hdu 5769后缀数组求含有某个字母的某个字符串的不同子串的个数

阅读量：4205 次

发布时间：2019-05-26

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

后缀数组可以处理重复子串所以我们直接用它的sa和height数组就行了，因为要满足有给定的字符，所以我们将sa[i]代表的串里有这个字符的全 部标记起来，只有这些才会对我们的结果有贡献值，然后正常的我们算不重复子串的个数是len-sa[i]-height[i]，但是现在有这样的情况，就是字 符是c，而sa[i]是dddcddd，那么它能贡献的值就是len-max((sa[i]+height[i]),c的位置)，因为若sa[i]+height[i]的值大于c的位置，这与正常的没有区 别，但是若c的位置大于sa[i]+height[i]，那么这个sa能贡献的就只有c位置和之后的串，所遇这里取个最大值就行了 #include 
   
      #include 
    
       #include 
     
        #include 
      
         #include 
       
          using namespace std;  typedef long long ll;  const int inf=0x3f3f3f3f;  const int MAXN=100010;  int sa[MAXN];  int t1[MAXN],t2[MAXN],c[MAXN];  int Rank[MAXN],height[MAXN];  void construct_sa(int s[],int n,int m){      int i,j,p,*x=t1,*y=t2;      for(i=0;i
        
         =0;i--)sa[--c[x[i]]]=i; for(j=1;j<=n;j<<=1){ p=0; for(i=n-j;i
         
          =j)y[p++]=sa[i]-j; for(i=0;i
          
           =0;i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(i=1;i
           
            =n)break; m=p; } } void construct_lcp(int s[],int n){ int k=0; for(int i=0;i<=n;i++) Rank[sa[i]]=i; for(int i=0;i
            
             =0;i--){ if(str[i]==ch[0]){ flag=1;fpr=i; } if(flag) fvis[i]=1,pr[i]=fpr; } ll ans=0; construct_sa(s,n+1,128); construct_lcp(s,n); for(int i=0;i<=n;i++){ if(fvis[sa[i]]) ans=ans+n-max((sa[i]+height[i]),pr[sa[i]]); } printf("Case #%d: %I64d\n",cas++,ans); } return 0; }