Milk Patterns

 

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

---

---

update:  2018-01-27

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

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

如何判断出现k次？

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

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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\n", r);81     }82 83 }
         
        
       
      

 

 

也可用哈希做，慢

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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--){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