[poj3261]Milk Patterns

求出后缀数组和height数组，然后二分答案后分组查询，一个块内如果有超过k个那么这个答案就可以。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 50005 4 int n,m,ans,a[N],b[N],h[N],sum[N],ra[N<<1],sa[N]; 5 char s[N],s1[N]; 6 void change(){ 7 for(int i=0;i<n;i++)a[i]=s[i]; 8 memcpy(ra,a,sizeof(a)); 9 sort(a,a+n); 10 m=unique(a,a+n)-a; 11 for(int i=0;i<n;i++)ra[i]=lower_bound(a,a+m,ra[i])-a+1; 12 } 13 void sort(int k){ 14 memset(sum,0,sizeof(sum)); 15 for(int i=0;i<n;i++)sum[ra[i+k]+1]++; 16 for(int i=1;i<=m;i++)sum[i+1]+=sum[i]; 17 for(int i=0;i<n;i++)b[sum[ra[a[i]+k]]++]=a[i]; 18 } 19 void build(){ 20 for(int i=1;;i<<=1){ 21 for(int j=0;j<n;j++)a[j]=j; 22 sort(i); 23 memcpy(a,b,sizeof(a)); 24 sort(0); 25 m=a[b[0]]=1; 26 for(int j=1;j<n;a[b[j++]]=m) 27 if ((ra[b[j-1]]!=ra[b[j]])||(ra[b[j-1]+i]!=ra[b[j]+i]))m++; 28 memcpy(ra,a,sizeof(a)); 29 if (m==n)break; 30 } 31 for(int i=0;i<n;i++)sa[ra[i]]=i; 32 } 33 void height(){ 34 m=0; 35 for(int i=0;i<n;h[ra[i++]]=m,m-=(m>0)) 36 for(int j=sa[ra[i]-1];(i!=j)&&(s[i+m]==s[j+m]);m++); 37 h[1]=0; 38 } 39 int lcp(int x,int y){ 40 int ans=0x3f3f3f3f; 41 if (ra[x]>ra[y])swap(x,y); 42 for(int i=ra[x]+1;i<=ra[y];i++)ans=min(ans,h[i]); 43 return ans; 44 } 45 void write(int x,int y){ 46 for(int i=x;i<=y;i++)printf("%c",s[i]); 47 } 48 int main(){ 49 int t; 50 scanf("%d",&t); 51 while (t--){ 52 scanf("%s",s); 53 n=strlen(s); 54 change(); 55 build(); 56 height(); 57 ans=0; 58 for(int i=1;i<=n;i++)ans+=n-sa[i]-h[i]; 59 printf("%d\n",ans); 60 } 61 } View Code

 

转载于:https://www.cnblogs.com/PYWBKTDA/p/11254712.html

总结

以上是生活随笔为你收集整理的[poj3261]Milk Patterns的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。