Milk Patterns POJ

Milk Patterns

题意：问长度为n的串中至少出现k次的子串最长是多长。

二分长度，再判断是否有子串重复k次。

 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