Description
农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。
Input
* Line 1: 两个整数 N,K。
* Lines 2..N+1: 每行一个整数表示当天的质量值。
Output
* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度
Sample Input
8 2
1
2
3
2
3
2
3
1
1
2
3
2
3
2
3
1
Sample Output
4
HINT
Source
Gold
Solution
SA模板题。
Tip：数字太大要离散化。
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=20010; int n,k,s[N],A[N],cnta[N],sa[N],rank[N*2],a[N],b[N],cntb[N],tsa[N],height[N]; void Get_SA() { for (int i=1;i<=n;i++) cnta[i]=0; for (int i=1;i<=n;i++) cnta[s[i]]++; for (int i=1;i<=n;i++) cnta[i]+=cnta[i-1]; for (int i=n;i>=1;i--) sa[cnta[s[i]]--]=i; rank[sa[1]]=1; for (int i=2;i<=n;i++) rank[sa[i]]=rank[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]); for (int i=1;rank[sa[n]]!=n;i<<=1) { for (int j=1;j<=n;j++) a[j]=rank[j],b[j]=rank[j+i]; for (int j=0;j<=n;j++) cnta[j]=0,cntb[j]=0; for (int j=1;j<=n;j++) cnta[a[j]]++,cntb[b[j]]++; for (int j=1;j<=n;j++) cnta[j]+=cnta[j-1],cntb[j]+=cntb[j-1]; for (int j=n;j>=1;j--) tsa[cntb[b[j]]--]=j; for (int j=n;j>=1;j--) sa[cnta[a[tsa[j]]]--]=tsa[j]; rank[sa[1]]=1; for (int j=2;j<=n;j++) rank[sa[j]]=rank[sa[j-1]]+(a[sa[j]]!=a[sa[j-1]]||b[sa[j]]!=b[sa[j-1]]); } } void Get_Height() { int len=0; for (int i=1;i<=n;i++) { if (len) len--; while (s[i+len]==s[sa[rank[i]-1]+len]) len++; height[rank[i]]=len; } } bool check(int x) { int tot=0; for (int i=2;i<=n;i++) { if (height[i]>=x) tot++;else tot=0; if (tot>=k-1) return 1; } return 0; } int erfen(int l,int r) { while (l<r) { int mid=(l+r+1)/2; if (check(mid)) l=mid;else r=mid-1; } return l; } int main() { scanf("%d%d",&n,&k); int cnt=0; for (int i=1;i<=n;i++) { scanf("%d",&s[i]); A[++cnt]=s[i]; } sort(A+1,A+cnt+1); cnt=unique(A+1,A+cnt+1)-A-1; for (int i=1;i<=n;i++) s[i]=lower_bound(A+1,A+n+1,s[i])-A; Get_SA(); Get_Height(); printf("%d\n",erfen(0,n)); return 0; } |
