UOJ35 后缀排序
后缀数组裸题中的裸题
一堆for也真是哔了狗了
每天早自习要背一遍代码才好=-=
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
// <35.cpp> - 02/02/16 11:48:31 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int MAXN=100005; string s; int n; int sa[MAXN],rk[MAXN]; int v[MAXN],x[MAXN],y[MAXN]; int h[MAXN]; void go(){ int m=29; for(int i=1;i<=n;i++)v[x[i]=(s[i]-'a'+1)]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[i]]--]=i; for(int j=1;j<=n;j<<=1){ int p=0; for(int i=n-j+1;i<=n;i++)y[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j; for(int i=1;i<=m;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[y[i]]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[y[i]]]--]=y[i]; swap(x,y);x[sa[1]]=1; p=1; for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p; if(p==n)break;m=p; } } void calh(){ int k=0,j; for(int i=1;i<=n;i++)rk[sa[i]]=i; for(int i=1;i<=n;h[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++); } int main(){ getline(cin,s); n=s.size();s='{'+s; go();calh(); for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts(""); for(int i=2;i<=n;i++)printf("%d ",h[i]); return 0; } |
POJ2774 Long Long Message
把两个字符串接起来，中间加个别的分隔符，求h[i]中sa[i]和sa[i-1]在不同字符串的最大值。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
// <2774.cpp> - 02/02/16 11:48:31 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int MAXN=200010; string s,s2; int n; int sa[MAXN],rk[MAXN]; int v[MAXN],x[MAXN],y[MAXN]; int h[MAXN]; void go(){ int m=29; for(int i=1;i<=n;i++)v[x[i]=(s[i]-'a'+1)]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[i]]--]=i; for(int j=1;j<=n;j<<=1){ int p=0; for(int i=n-j+1;i<=n;i++)y[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j; for(int i=1;i<=m;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[y[i]]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[y[i]]]--]=y[i]; swap(x,y);x[sa[1]]=1; p=1; for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p; if(p==n)break;m=p; } } void calh(){ int k=0,j; for(int i=1;i<=n;i++)rk[sa[i]]=i; for(int i=1;i<=n;h[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++); } int main(){ getline(cin,s);getline(cin,s2); int l1=s.size(),ans=0; s='{'+s+'}'+s2; n=s.size()-1; go();calh(); for(int i=2;i<=n;i++)if((sa[i]<=l1)^(sa[i-1]<=l1))ans=max(ans,h[i]); cout<<ans; return 0; } |
POJ1743 Musical Theme
将点转化为差值。。然后二分找最长不重叠重复子串。。然后把答案+1再和5判断一下就完了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
// <1743.cpp> - 02/02/16 11:48:31 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=20010; int n; int a[MAXN],s[MAXN],sa[MAXN],rk[MAXN]; int v[MAXN],x[MAXN],y[MAXN]; int h[MAXN]; void go(){ int m=180; for(int i=1;i<=n;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[i]=s[i]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[i]]--]=i; for(int j=1;j<=n;j<<=1){ int p=0; for(int i=n-j+1;i<=n;i++)y[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j; for(int i=1;i<=m;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[y[i]]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[y[i]]]--]=y[i]; swap(x,y);x[sa[1]]=1; p=1; for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p; if(p==n)break;m=p; } } void calh(){ int k=0,j; for(int i=1;i<=n;i++)rk[sa[i]]=i; for(int i=1;i<=n;h[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++); } bool check(int m){ int l=sa[1],r=l; for(int i=2;i<=n;i++){ if(h[i]<m){l=r=sa[i];continue;} if(sa[i]<l)l=sa[i]; if(sa[i]>r)r=sa[i]; if(r-l>m)return 1; } return 0; } int main(){ while(1){ n=getint(); if(!n)break; for(int i=1;i<=n;i++)a[i]=getint(); for(int i=2;i<=n;i++)s[i-1]=a[i]-a[i-1]+90;n--; go();calh(); int l=0,r=n>>1; while(l<r){ int m=(l+r+1)>>1; if(check(m))l=m; else r=m-1; } cout<<(l+1<5?0:l+1)<<endl; } return 0; } |
POJ3261 Milk Patterns
寻找可重叠的至少出现了K次的最长子串。。
可重叠的话方便多了 判断一下次数大于K即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// <3261.cpp> - 02/02/16 11:48:31 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=20010; const int M=1000002; int n,K; int a[MAXN],s[MAXN],sa[MAXN],rk[MAXN]; int v[M+10],x[MAXN],y[MAXN]; int h[MAXN]; void go(){ int m=M; for(int i=1;i<=n;i++)v[x[i]=s[i]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[i]]--]=i; for(int j=1;j<=n;j<<=1){ int p=0; for(int i=n-j+1;i<=n;i++)y[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j; for(int i=1;i<=m;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[y[i]]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[y[i]]]--]=y[i]; swap(x,y);x[sa[1]]=1; p=1; for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p; if(p==n)break;m=p; } } void calh(){ int k=0,j; for(int i=1;i<=n;i++)rk[sa[i]]=i; for(int i=1;i<=n;h[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++); } bool check(int m){ int tot=1; for(int i=2;i<=n;i++){ if(h[i]<m)tot=1; else if(++tot>=K)return 1; } return 0; } int main(){ n=getint();K=getint(); for(int i=1;i<=n;i++)s[i]=getint()+1; go();calh(); int l=0,r=n; while(l<r){ int m=(l+r+1)>>1; if(check(m))l=m; else r=m-1; } cout<<l<<endl; return 0; } |