http://poj.org/problem?id=3261 給一串數組，數組最少含有k個相同子串，可重疊，求這樣子串的最長長度。 后綴數組求出?height[]，若連續k個height[]都大于mid，就可以了。當然要找最大的mid，這里可用二分查找.。 關于后綴數組可以參考：http://hi.baidu.com/fhnstephen/blog/item/4b20757c37245d0429388a76.html #include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; const int maxn = 1000005; const int maxm = 1000001; int wa[maxn], wb[maxn]; int r[maxn], b[1000001]; int rank[maxn]; int num[maxn], sa[maxn]; int height[200001]; int cmp (int *r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l]; } void make_sa(int n, int m){ int i, j, p, *x = wa, *y = wb; for (i = 0; i < m; i++) b[i] = 0; for (i = 0; i < n; i++) b[x[i] = num[i]]++; for (i = 1; i < m; i++) b[i] += b[i-1]; for (i = n-1; i >= 0; i--) sa[--b[x[i]]] = i; for (j = 1, p=1; p < n; j*=2, m = p){ for (p = 0, i = n-j; i<n; i++) y[p++] = i; for (i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j; for (i = 0; i < n; i++) r[i] = x[y[i]]; for (i = 0; i < m; i++) b[i] = 0; for (i = 0; i < n; i++) b[r[i]]++; for (i = 1; i < m; i++) b[i] += b[i-1]; for (i = n-1; i>= 0; i--) sa[--b[r[i]]] = y[i]; int *t = x; x = y; y = t; for (i = p = 1, x[sa[0]] = 0; i < n; i++) x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1:p++; } return; } void calheight(int len) { int i,j,k=0; for (i =1; i<len+1; i++) rank[sa[i]] = i; for(i=0;i<len;height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];num[i+k]==num[j+k];k++); return ; } int k; bool judge(int key,int len) { int ssum=0; for(int i=1;i<len;i++) { if(height[i]>=key) { ssum++; if(ssum+1>=k) { return true; } } else{ ssum=0; } } return false; } int main() { int n,i; while(scanf("%d%d",&n,&k)!=EOF) { for(i=0;i<n;i++) { scanf("%d",&num[i]); } num[n]=0; make_sa(n+1,maxm); calheight(n); int low=1,hight=n; while(low<=hight) { int mid=(low+hight)>>1; if(judge(mid,n+1)) { low=mid+1; } else{ hight=mid-1; } } if(hight<n) { printf("%d\n",hight); } } return 0; }

轉載于:https://www.cnblogs.com/zxj015/archive/2011/03/19/2740273.html

總結

以上是生活随笔為你收集整理的poj 3261 Milk Patterns 后缀数组 最长重复子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。