后缀数组。
这两天都在研究罗穗骞神牛的《后缀数组——处理字符串的有力工具》，很久以前就听过的数据结构，现在总算用到了。
题意是给出一个长20000的数组，值范围是1到88，问是否存在长度大于等于5的一个子串，其满足“变调”后非重叠地出现在原数组的其他位置。这里变调的意思是整个子串同时加上或减去某个值。
分析题意后可以发现，如果取值间的差值建立一个新数组，那么新数组上长度为m的非重叠重复出现的子串对应着原数组中长度为m+1的子串。这样就解决了“变调”的问题。
进一步分析，可以发现可以二分答案：对于某个值l，当m<=l时满足题意的子串总存在。从而将问题转化为判定性问题。 然后对每次枚举的m值，使用后缀数组建立的height[]，便可O(n)地判断是否可行了。 不过由于建立数组时我只实现了基于快排的二倍增，因此总体复杂度被拖低成O(n(lgn)^2)了，g++下跑了610ms。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,d[40000],sa[40000],r[40000],h[40000]; struct E { int i,r; bool operator < (const E &p) const { return r<p.r; } }e[40000]; int gi() { char c; while((c=getchar())<'0'||c>'9'); int d=c-'0'; while((c=getchar())>='0'&&c<='9') d=d*10+c-'0'; return d; } void init() { memset(d,0,sizeof d); memset(sa,0,sizeof sa); memset(r,0,sizeof r); memset(h,0,sizeof h); memset(e,0,sizeof e); int i,j,k,l; j=gi(); n--; for(i=0;i<n;i++) { k=gi(); e[i].i=i; d[i]=e[i].r=k-j+88; j=k; } sort(e,e+n); r[e[0].i]=1; for(i=j=1;i<n;i++) { if(e[i].r==e[i-1].r) r[e[i].i]=j; else r[e[i].i]=++j; } for(l=1;l<n;l<<=1) { for(i=0;i<n;i++) { e[i].i=i; e[i].r=r[i]*(n+1)+r[i+l]; } sort(e,e+n); r[e[0].i]=1; for(i=j=1;i<n;i++) { if(e[i].r==e[i-1].r) r[e[i].i]=j; else r[e[i].i]=++j; } } for(i=0;i<n;i++) sa[r[i]-1]=i; for(i=0;i<n;i++) r[sa[i]]=i; for(i=k=0;i<n;i++) { if(!r[i]) continue; for(k?k--:0,j=sa[r[i]-1];d[i+k]==d[j+k];k++); h[r[i]]=k; } } int calc(int m) { int i,mn,mx; for(i=1,mx=mn=-1;i<n;i++) { if(h[i]<m) { if(mx!=-1&&mx-mn>m) return 1; mx=mn=-1; } else { if(mx==-1) { mx=max(sa[i],sa[i-1]); mn=min(sa[i],sa[i-1]); } else { mx=max(mx,sa[i]); mn=min(mn,sa[i]); } } } if(mx!=-1&&mx-mn>m) return 1; return 0; } void solve() { int l,h,m; for(l=3,h=n/2;l<h;) { m=l+h+1>>1; if(calc(m)) l=m; else h=m-1; } if(l==3) puts("0"); else printf("%d\n",l+1); } int main() { while(n=gi()) { init(); solve(); } return 0; } |
另外，这题之前也已经用字符串hash做过了的（半年前还在用数组实现hash表），竟然比后缀数组还要快些（g++ 438ms）……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<cstdio> #include<cstring> int n,a[20000],b[20000],hs[10007][20]; int gi() { char c; while((c=getchar())<'0'||c>'9'); int d=c-'0'; while((c=getchar())>='0'&&c<='9') d=d*10+c-'0'; return d; } int ck(int m) { int i,j,l,h,k,g; memset(hs,0,sizeof(hs)); for(j=0,k=0,g=1;j<m-1;j++) { k=(k*131+b[j])%10007; g=(g*131)%10007; } hs[k][++hs[k][0]]=0; for(i=1;i<n-m+1;i++) { k=k*131+b[i+m-2]+10007; k-=g*b[i-1]%10007; k%=10007; if(hs[k][0]) { for(j=1;j<=hs[k][0];j++) { h=hs[k][j]; if(i-h<m) continue; for(l=0;l<m-1&&b[i+l]==b[h+l];l++); if(l==m-1) return 1; } } hs[k][++hs[k][0]]=i; } return 0; } int main() { int i,l,h,m; while(n=gi()) { for(i=0;i<n;i++) a[i]=gi(); for(i=0;i<n-1;i++) b[i]=a[i]-a[i+1]+88; for(l=5,h=n/2;l<h;) { m=l+h+1>>1; if(ck(m)) l=m; else h=m-1; } if(ck(l)) printf("%d\n",l); else puts("0"); } return 0; } |
ps: 又发现了一个很有趣的blog：Summer’s Mariner。