后缀数组(至少重复k次的可重叠的最长重复子串)—— POJ 3882
对应POJ 题目:点击打开链接
思路:后缀数组的基础应用,二分答案分组求最大长度不是问题,反而在求下标那卡了一下。。。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MS(x, y) memset(x, y, sizeof(x)) const int MAXN = 40000+10; int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; int rank[MAXN],r[MAXN],sa[MAXN],height[MAXN]; char str[MAXN]; int cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r, int *sa, int n, int m) { int i, j, p, *x = wa, *y = wb, *t; for(i=0; i<m; i++) ws[i] = 0; for(i=0; i<n; i++) ws[x[i] = r[i]]++; for(i=1; i<m; i++) ws[i] += ws[i-1]; for(i=n-1; i>=0; i--) sa[--ws[x[i]]] = i; for(j=1,p=1; p<n; j<<=1, 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++) wv[i] = x[y[i]]; for(i=0; i<m; i++) ws[i] = 0; for(i=0; i<n; i++) ws[wv[i]]++; for(i=1; i<m; i++) ws[i] += ws[i-1]; for(i=n-1; i>=0; i--) sa[--ws[wv[i]]] = y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++; } return; } void calheight(int *r, int *sa, int n) { int i, j, k = 0; for(i=1; i<n; i++) rank[sa[i]] = i; for(i=0; i<n-1; height[rank[i++]] = k) for(k ? k-- : 0,j=sa[rank[i]-1]; r[i+k] == r[j+k]; k++); return; } int main() { //freopen("in.txt", "r", stdin); int n; while(~scanf("%d", &n), n) { MS(rank, 0); MS(sa, 0); MS(wa, 0); MS(wb, 0); MS(ws, 0); MS(wv, 0); MS(r, 0); MS(height, 0); scanf("%s", str); int len = strlen(str); if(1 == n){ printf("%d 0\n", len); continue; } int maxn = 0; for(int i=0; i<len; i++){ r[i] = str[i] - 'a' + 1; if(r[i] > maxn) maxn = r[i]; } r[len++] = 0;//末尾添加一个最小值 da(r, sa, len, maxn+1); calheight(r, sa, len); #if 0 printf("rank : "); for(int i=0; i<len; i++) printf(" %d", rank[i]); printf("\n"); printf("sa : "); for(int i=0; i<len; i++) printf(" %d", sa[i]); printf("\n"); printf("height: "); for(int i=0; i<len; i++) printf(" %d", height[i]); printf("\n"); #endif int left = 0, right = len-1; int mlen = 0, max1 = 0, max2 = 0, max3 = 0; int beg = 0, end = 0, ok; while(left <= right) { ok = 0; int mid = left + (right - left)/2;//二分答案 max1 = max2 = 0; for(int i=2; i<len; i++){ if(height[i] >= mid){//确定某一组的起点终点 if(!beg) beg = i; end = i; } if((beg && end) && (i == len - 1 || height[i] < mid)){ if(end - beg + 2 >= n){//符合题意的组 max1 = 0; for(int i=beg-1; i<=end; i++)//求该组最右边的下标 if(sa[i] > max1) max1 = sa[i]; mlen = mid; if(max1 > max2) max2 = max1; ok = 1; } beg = end = 0; } } if(ok) max3 = max2; if(ok) left = mid + 1; else right = mid - 1; } if(mlen) printf("%d %d\n", mlen, max3); else printf("none\n"); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。