首页 > 代码库 > 【POJ3261】Milk Patterns 后缀数组
【POJ3261】Milk Patterns 后缀数组
水题不好意思说题解。
说说题意吧:
给一个字符串(数字串),然后求最长k次重复子串。
即某串在字符串中重复了至少k次,求这种串的最长长度。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 21000 using namespace std; struct LSH { int x,id; bool operator < (const LSH &a)const{return x<a.x;} }lsh[N]; int s[N]; int sa[N],rank[N],h[N],n,m,len; int cnt[N],val[N],stk[N],_val[N],top; bool issame(int a,int b,int hl) { return val[a]==val[b]&& ((a+hl>=len&&b+hl>=len)||(a+hl<len&&b+hl<len&&val[a+hl]==val[b+hl])); } void SA(int lim) { int i,j,k,hl; for(i=0;i<lim;i++)cnt[i]=0; for(i=0;i<len;i++)cnt[val[i]=s[i]]++; for(i=1;i<lim;i++)cnt[i]+=cnt[i-1]; for(i=len-1;i>=0;i--)sa[--cnt[val[i]]]=i; for(k=1;;k++) { top=0,hl=1<<(k-1); for(i=0;i<len;i++)if(sa[i]+hl>=len)stk[top++]=sa[i]; for(i=0;i<len;i++)if(sa[i]>=hl)stk[top++]=sa[i]-hl; for(i=0;i<lim;i++)cnt[i]=0; for(i=0;i<len;i++)cnt[val[i]]++; for(i=1;i<lim;i++)cnt[i]+=cnt[i-1]; for(i=len-1;i>=0;i--)sa[--cnt[val[stk[i]]]]=stk[i]; for(lim=i=0;i<len;lim++) { for(j=i;j<len-1&&issame(sa[j],sa[j+1],hl);j++); for(;i<=j;i++)_val[sa[i]]=lim; } for(i=0;i<len;i++)val[i]=_val[i]; if(lim==len)break; } for(i=0;i<len;i++)rank[sa[i]]=i; for(k=i=0;i<len;i++) { if(k)k--; if(!rank[i])continue; while(s[i+k]==s[sa[rank[i]-1]+k])k++; h[rank[i]]=k; } } int K; bool check(int mid) { int num=1,i; for(i=0;i<len;i++) { if(h[i]>=mid)num++; else num=1; if(num>=K)return 1; } return 0; } int main() { // freopen("test.in","r",stdin); int i,j,k; while(scanf("%d%d",&len,&K)!=EOF) { for(i=0;i<len;i++)scanf("%d",&lsh[i].x),lsh[i].id=i; sort(lsh,lsh+len); int nm=0; for(i=0;i<len;i++) { if(i==0||lsh[i].x!=lsh[i-1].x)nm++; s[lsh[i].id]=nm; } SA(20000); int l=0,r=len,mid,ans=0; while(l<=r) { if(r-l<=3) { for(i=l;i<=r;i++)if(check(i))ans=i; break; } mid=l+r>>1; if(check(mid))l=mid; else r=mid; } printf("%d\n",ans); } return 0; }
【POJ3261】Milk Patterns 后缀数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。