题目链接:
题意:
给你一个字符串,让你找不重叠且出现大于1次以上的字串个数
题解:
后缀数组height数组的应用,我们枚举字串的长度,然后将height数组分段,符合条件就ans++
为什么要这样做,因为height数组存的是相邻排名后缀的最大前缀数,如果height的值大于等于我们枚举的长度len,
那么有可能这一段存在有两个以上的该长度的字串,然后我们统计这个段的开头长度l和结束长度r,如果r-l>=len,说明这段必有
大于一个以上的该长度的相同子串,因为我们每次都是枚举len,按len分的段,所以不会重复。
1 #include2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 namespace suffixarray{ 6 #define FN(n) for(int i=0;i =0;i--)sa[--c[x[i]]]=i;12 for(int k=1,p;p=0,k<=n;k=p>=n?N:k<<1,m=p){13 for(int i=n-k;i =k)y[p++]=sa[i]-k;15 FN(m)c[i]=0;FN(n)c[x[y[i]]]++;FN(m)c[i+1]+=c[i];16 for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];17 swap(x,y),p=1,x[sa[0]]=0;18 for(int i=1;i b)a=b;}28 inline void upu(int &a,int b){ if(a =i)upd(l,sa[j]),upu(r,sa[j]);43 else44 {45 if(r-l>=i)ans++;46 l=r=sa[j];47 }48 }49 if(r-l>=i)ans++;50 }51 printf("%d\n",ans);52 }53 return 0;54 }