hdu_3518_Boring counting(后缀数组)

题意：

给你一个字符串，让你找不重叠且出现大于1次以上的字串个数

题解：

后缀数组height数组的应用，我们枚举字串的长度，然后将height数组分段，符合条件就ans++

为什么要这样做，因为height数组存的是相邻排名后缀的最大前缀数，如果height的值大于等于我们枚举的长度len，

那么有可能这一段存在有两个以上的该长度的字串，然后我们统计这个段的开头长度l和结束长度r，如果r-l>=len，说明这段必有

大于一个以上的该长度的相同子串，因为我们每次都是枚举len,按len分的段，所以不会重复。

 #include<bits/stdc++.h>

 #define F(i,a,b) for(int i=a;i<=b;++i)

 using namespace std;

 namespace suffixarray{

     #define FN(n) for(int i=0;i<n;i++)

     const int N =1E3+;

     int rnk[N],sa[N],height[N],c[N];char s[N];

     void getsa(int n,int m,int *x=rnk,int *y=height){

         FN(m)c[i]=;FN(n)c[x[i]=s[i]]++;FN(m)c[i+]+=c[i];

         for(int i=n-;i>=;i--)sa[--c[x[i]]]=i;

         for(int k=,p;p=,k<=n;k=p>=n?N:k<<,m=p){

             for(int i=n-k;i<n;i++)y[p++]=i;

             FN(n)if(sa[i]>=k)y[p++]=sa[i]-k;

             FN(m)c[i]=;FN(n)c[x[y[i]]]++;FN(m)c[i+]+=c[i];

             for(int i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];

             swap(x,y),p=,x[sa[]]=;

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

             x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;

         }

         FN(n)rnk[sa[i]]=i;

         for(int i=,j,k=;i<n-;height[rnk[i++]]=k)

         for(k=k?k-:k,j=sa[rnk[i]-];s[i+k]==s[j+k];k++);

     }

 }

 inline void upd(int &a,int b){if(a>b)a=b;}

 inline void upu(int &a,int b){if(a<b)a=b;}

 using namespace suffixarray;

 int main(){

     while(~scanf("%s",s))

     {

         if(s[]=='#')break;

         int len=strlen(s),ans=;

         getsa(len+,);

         F(i,,len)

         {

             int l=len+,r=;

             F(j,,len)

             {

                 if(height[j]>=i)upd(l,sa[j]),upu(r,sa[j]);

                 else

                 {

                     if(r-l>=i)ans++;

                     l=r=sa[j];

                 }

             }

             if(r-l>=i)ans++;

         }

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

     }

     return ;

 }

巴特西

hdu_3518_Boring counting(后缀数组)

最新文章

热门文章