首页 > 代码库 > 【POJ】1743 Musical Theme
【POJ】1743 Musical Theme
http://poj.org/problem?id=1743
题意:不可重叠最长重复子串,n<=20000,具体看《后缀数组》-- 罗穗骞
#include <cstdio>#include <algorithm>using namespace std;const int N=20015;void sort(int *x, int *y, int *sa, int n, int m) { static int c[N], i; for(i=0; i<m; ++i) c[i]=0; for(i=0; i<n; ++i) c[x[y[i]]]++; for(i=1; i<m; ++i) c[i]+=c[i-1]; for(i=n-1; i>=0; --i) sa[--c[x[y[i]]]]=y[i];}void hz(int *r, int *sa, int n, int m) { static int t1[N], t2[N]; static int *x, *y, *t, j, i, p=0; x=t1; y=t2; for(i=0; i<n; ++i) x[i]=r[i], y[i]=i; sort(x, y, sa, n, m); for(j=1, p=1; p<n; j<<=1, m=p) { p=0; for(i=n-j; i<n; ++i) y[p++]=i; for(i=0; i<n; ++i) if(sa[i]-j>=0) y[p++]=sa[i]-j; sort(x, y, sa, n, m); for(t=x, x=y, y=t, x[sa[0]]=0, p=1, i=1; i<n; ++i) x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p-1:p++; }}void geth(int *a, int *sa, int *rank, int *h, int n) { static int k, i, j; k=0; for(i=1; i<=n; ++i) rank[sa[i]]=i; for(i=1; i<=n; h[rank[i++]]=k) for(k?--k:0, j=sa[rank[i]-1]; a[i+k]==a[j+k]; ++k);}const int oo=~0u>>2;int sa[N], rank[N], h[N], n, a[N];bool check(int k) { int mx=sa[1], mn=sa[1]; for(int i=2; i<=n; ++i) { if(h[i]>=k) { mx=max(mx, sa[i]); mn=min(mn, sa[i]); if(mx-mn>=k) return 1; } else mx=sa[i], mn=sa[i]; } return 0;}int main() { while(scanf("%d", &n), n) { scanf("%d", &a[1]); --n; for(int i=1; i<=n; ++i) scanf("%d", &a[i+1]), a[i]=a[i+1]-a[i]+100; hz(a, sa, n+1, 200); geth(a, sa, rank, h, n); int mid, l=0, r=n/2; while(l<=r) { mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } if(l>=5) printf("%d\n", l); else puts("0"); } return 0;}
经典题....我们求出height数组后,按二分的大小k分组。即每个组里的height值都要>=k,然后看每个块是否有sa值之差>=k的即可
(吐槽:poj不能用bits/stdc++.h啊啊啊啊啊啊ce了两发啊...
【POJ】1743 Musical Theme
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。