首页 > 代码库 > Bzoj2882 工艺 [香港算法]
Bzoj2882 工艺 [香港算法]
后缀自动机题解 -> http://www.cnblogs.com/SilverNebula/p/6420601.html
后缀自动机敲完，看了下排行，wc为什么别人跑得这么快？……是诶，这最小表示法用后缀自动机当然慢了
依稀记得最小表示法有超快的算法，于是去查了查，有O(n)的算法 (后缀自动机均摊也是O(n)然而常数大)
找到了这篇讲解-> http://www.cnblogs.com/mjy0724/p/4625928.html
这样就跑得飞快了(380ms，不知道那些几十ms的怎么跑出来的)
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=600010; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int n,a[mxn];16 int solve(){17 int i,j,ed=n*2;18 i=1;j=2;19 while(i<=n && j<=n){20 int k=0;21 while(j+k<=ed && a[i+k]==a[j+k])k++;22 if(j+k>ed)break;23 if(a[i+k]>a[j+k]){24 i=max(j,i+k+1);25 j=i+1;26 }27 else j=j+k+1;28 }29 return min(i,j);30 }31 int main(){32 int i,j;33 n=read();34 for(i=1;i<=n;i++){35 a[i]=read();a[i+n]=a[i];36 }37 int ans=solve();38 int ed=ans+n-1;39 for(i=ans;i<ed;i++)printf("%d ",a[i]);40 printf("%d\n",a[ed]);41 return 0;42 }
Bzoj2882 工艺 [香港算法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。