Milk Patterns POJ

Milk Patterns

POJ - 3261

第一道后缀数组，，有点蒙逼=_=

update: 2018-01-27

题意：求至少出现k次的最长子串的长度。

可以二分长度mid，看是否能出现k次。

如何判断出现k次？

由后缀数组的height数组，将height数组按顺序分组，每一组内的最长公共前缀不小于mid（小于mid的自成一组），统计最大组的height个数即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 #define FP freopen("in.txt","r".stdin);
 7 
 8 const int maxn=20010;
 9 int s[maxn], s1[maxn];
10 int sa[maxn], t[maxn], t2[maxn], c[maxn], n, k;
11 int rank[maxn], height[maxn];
12 
13 void build_sa(int m, int n){
14     int i, *x=t, *y=t2;
15     //基数排序
16     for(i = 0; i < m; i++) c[i] = 0;
17     for(i = 0; i < n; i++) c[x[i] = s[i]]++;
18     for(i = 1; i < m; i++) c[i] += c[i-1];
19     for(i = n-1;i >= 0; i--) sa[--c[x[i]]] = i;
20 
21     for(int k = 1; k <= n; k <<= 1){
22         int p=0;
23         //直接利用sa数组排序第二关键字
24         for(i = n-k; i < n; i++) y[p++] = i;
25         for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
26 
27         //基数排序第一关键字
28         for(i = 0; i < m; i++) c[i] = 0;
29         for(i = 0; i < n; i++) c[x[y[i]]]++;
30         for(i = 1; i < m; i++) c[i] += c[i-1];
31         for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
32         //根据sa和y数组计算新的x数组
33         swap(x, y);
34         p = 1;
35         x[sa[0]] = 0;
36         for(i = 1; i < n; i++) 
37           x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k] ? p-1 : p++;
38 
39         if(p >= n) break;  //以后即使继续倍增，sa也不会改变，推出
40         m = p;          //下次基数排序的最大值
41     }
42 }
43 
44 void getHeight(int n) {
45     int i, j, k = 0;
46     for(i = 0; i <= n; i++) rank[sa[i]] = i;
47     for(i = 0; i < n; i++) {
48         if(k) k--;
49         j = sa[rank[i]-1];
50         while(s[i+k] == s[j+k]) k++;
51         height[rank[i]] = k;
52     }
53 }
54 int m; //模板长度
55 
56 int main(){
57     while(scanf("%d%d", &n, &k)!=EOF){
58         for(int i = 0; i < n; i++) scanf("%d",&s[i]);
59         for(int i = 0; i < n; i++) s1[i] = s[i];
60         sort(s, s+n);
61         int sz=unique(s,s+n)-s;
62         for(int i = 0; i < n; i++) {
63             s1[i]=lower_bound(s,s+sz,s1[i])-s+1;
64         }
65         for(int i = 0; i <= n; i++) s[i]=s1[i];
66         build_sa(256, n+1);
67         getHeight(n);
68         int l=1, r=n;
69         while(l <= r) { 
70             int cnt=1;
71             int m=(l+r)>>1;
72             for(int i = 1; i <= n; i++){
73                 if(height[i] >= m) cnt++;
74                 else cnt=1;
75                 if(cnt>=k) break;
76             }
77             if(cnt >= k) l=m+1;
78             else r=m-1;
79         }
80         printf("%d
", r);
81     }
82 
83 }

View Code

也可用哈希做，慢

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 #define ull unsigned long long
 7 const int maxn=20010;
 8 const int seed=131;
 9 
10 ull base[maxn],h[maxn];
11 int a[maxn];
12 int n,k;
13 
14 int check(int m)
15 {
16     memset(h,0,sizeof(h));
17     for(int i=0;i<m;i++) h[m-1]=h[m-1]*seed+a[i];
18     for(int i=m;i<n;i++){
19         h[i]=h[i-1]*seed-a[i-m]*base[m]+a[i];
20     }
21     sort(h,h+n);
22     int cnt=1;
23     for(int i=n-1;i>=m;i--){
24         if(h[i]==h[i-1]) cnt++;
25         else cnt=1;
26         if(cnt>=k) return 1;
27     }
28     return 0;
29 }
30 int main()
31 {
32     base[0]=1;
33     for(int i=1;i<maxn;i++) base[i]=base[i-1]*seed;
34     while(scanf("%d%d",&n,&k)!=EOF){
35         for(int i=0;i<n;i++){
36             scanf("%d",&a[i]);
37         }
38         int L=0,R=n;
39         while(L<=R){
40             int m=L+(R-L)/2;
41             if(check(m)) L=m+1;
42             else R=m-1;
43         }
44         printf("%d
",R);
45     }
46 }

View Code