首页 > 代码库 > poj 1743 Musical Theme【后缀自动机】
poj 1743 Musical Theme【后缀自动机】
不是很神的一道题,一般。
先差分,最后答案需要+1。
一个right集的len即为该right集的最长相同后缀,考虑到不能重复,所以处理一下该right集的最大与最小的ri,最后答案ans=max(ans,min(r[i]-l[i],len[i]))
poj的g++比较恶心,卡空间,卡时间。
用c++交即可。
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<iomanip> #include<set> #include<map> #include<queue> using namespace std; #define mem1(i,j) memset(i,j,sizeof(i)) #define mem2(i,j) memcpy(i,j,sizeof(i)) #define LL long long #define up(i,j,n) for(int i=(j);i<=(n);i++) #define FILE "dealing" #define poi vec #define eps 1e-10 #define db double const int maxn=40005,inf=1000000000,mod=1000000007; int read(){ int x=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar();} return f*x; } bool cmax(int& a,int b){return a<b?a=b,true:false;} bool cmin(int& a,int b){return a>b?a=b,true:false;} int a[maxn],l[maxn],r[maxn]; int cnt=1,now=1; int pre[maxn],len[maxn],ct[maxn],sa[maxn],np,p,q,nq; int c[maxn][180]; void extend(int x){ p=now;np=++cnt;len[np]=len[p]+1;now=np;l[np]=r[np]=len[np]; while(p&&!c[p][x])c[p][x]=np,p=pre[p]; if(!p)pre[np]=1; else { q=c[p][x]; if(len[q]==len[p]+1)pre[np]=q; else { len[nq=++cnt]=len[p]+1; mem2(c[nq],c[q]); pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(p&&c[p][x]==q) c[p][x]=nq,p=pre[p]; } } } void getsort(){ mem1(ct,0);mem1(sa,0); up(i,1,cnt)ct[len[i]]++; up(i,1,cnt)ct[i]+=ct[i-1]; for(int i=cnt;i>=1;i--)sa[ct[len[i]]--]=i; } void clear(){ mem1(pre,0);mem1(len,0);cnt=1,now=1;mem1(c,0); } void build(int* s,int n){ clear(); up(i,1,n) extend(s[i]); } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); while(true){ mem1(l,10);mem1(r,0); int n=read();if(!n)break; up(i,1,n)a[i]=read(); up(i,1,n-1)a[i]=a[i+1]-a[i]+87;n--; build(a,n); getsort();int *t=sa; for(int i=cnt;i>=1;i--){ r[pre[t[i]]]=max(r[pre[t[i]]],r[t[i]]); l[pre[t[i]]]=min(l[pre[t[i]]],l[t[i]]); } int ans=-1e9; up(i,2,cnt)ans=max(ans,min(r[i]-l[i],len[i])); printf("%d\n",ans<4?0:ans+1); } return 0; }
poj 1743 Musical Theme【后缀自动机】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。