首页 > 代码库 > Milk Patterns
Milk Patterns
poj3261:http://poj.org/problem?id=3261
题意:
题解:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=20010; 6 char str[maxn]; 7 int wa[maxn],wb[maxn],wv[maxn],wn[maxn],a[maxn],sa[maxn]; 8 int num; 9 int cmp(int* r,int a,int b,int l)10 {11 return r[a]==r[b]&&r[a+l]==r[b+l];12 }13 //n为字符串长度,m为字符的取值范围,r为字符串。后面的j为每次排序时子串的长度14 void DA(int* r,int* sa,int n,int m)15 {16 int i,j,p,*x=wa,*y=wb,*t;17 ///对R中长度为1的子串进行基数排序18 for(i=0; i<m; i++)wn[i]=0;19 for(i=0; i<n; i++)wn[x[i]=r[i]]++;20 for(i=1; i<m; i++)wn[i]+=wn[i-1];21 for(i=n-1; i>=0; i--)sa[--wn[x[i]]]=i;22 for(j=1,p=1; p<n; j*=2,m=p)23 {24 //利用了上一次基数排序的结果,对待排序的子串的第二关键字进行了一次高效地基数排序25 for(p=0,i=n-j; i<n; i++)y[p++]=i;26 for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;27 ///基数排序28 for(i=0; i<n; i++)wv[i]=x[y[i]];29 for(i=0; i<m; i++)wn[i]=0;30 for(i=0; i<n; i++)wn[wv[i]]++;31 for(i=1; i<m; i++)wn[i]+=wn[i-1];32 for(i=n-1; i>=0; i--)sa[--wn[wv[i]]]=y[i];33 ///当p=n的时候,说明所有串都已经排好序了34 ///在第一次排序以后,rank数组中的最大值小于p,所以让m=p35 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)36 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;37 }38 return;39 }40 ///后缀数组 计算height数组41 /**42 height数组的值应该是从height[1]开始的,而且height[1]应该是等于0的。43 原因是,+因为我们在字符串后面添加了一个0号字符,所以它必然是最小的44 一个后缀。而字符串中的其他字符都应该是大于0的(前面有提到,使用倍45 增算法前需要确保这点),所以排名第二的字符串和0号字符的公共前缀46 (即height[1])应当为0.在调用calheight函数时,要注意height数组的范47 围应该是[1..n]。所以调用时应该是calheight(r,sa,n)48 而不是calheight(r,sa,n+1)。*/49 int rank[maxn],height[maxn];50 void calheight(int* r,int* sa,int n)51 {52 int i,j,k=0;53 for(i=1; i<=n; i++)rank[sa[i]]=i;54 for(i=0; i<n; height[rank[i++]]=k)55 for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);56 return;57 }58 int t;59 bool judge(int mid){60 int counts=0;61 for(int i=1;i<=t;i++){62 if(height[i]<mid){63 counts=0;64 }65 else{66 counts++;67 if(counts>=num-1)68 return true;69 }70 }71 72 return false;73 }74 int main(){75 while(~scanf("%d %d",&t,&num)&&t){76 for(int i=0;i<t;i++){77 scanf("%d",&a[i]);78 }79 a[t]=0;80 DA(a,sa,t+1,260);81 calheight(a,sa,t);82 int l=0,r=t,ans=0;83 while(l<=r){84 int mid=(l+r)/2;85 if(judge(mid)){86 ans=mid;87 l=mid+1;88 }89 else90 r=mid-1;91 }92 93 printf("%d\n",ans);94 }95 return 0;96 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。