SHARE
TWEET

Untitled

a guest Mar 28th, 2016 232 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define readFile freopen("inn.txt","r",stdin)
  4. #define writeFile freopen("out.txt","w",stdout)
  5. #define fastio ios_base::sync_with_stdio(false)
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1000010;
  10. int suffArr[N], tmpSuffArr[N], rankk[N], tmpRank[N],
  11.         lcp[N], plcp[N], pos[N], freq[N], lens[N], n, k;
  12. char s[N];
  13.  
  14. void countingSort(int k){
  15.     int mx = max(300,n+1), acum = 0;
  16.     memset(freq,0,sizeof(freq));
  17.     for(int i = 0; i < n; i++) freq[i+k < n ? rankk[i+k] : 0]++;
  18.     for(int i = 0; i < mx; i++){
  19.         int t = freq[i];
  20.         freq[i] = acum;
  21.         acum += t;
  22.     }
  23.     for(int i = 0; i < n; i++) tmpSuffArr[freq[suffArr[i]+k < n ? rankk[suffArr[i]+k] : 0]++] = suffArr[i];
  24.     for(int i = 0; i < n; i++) suffArr[i] = tmpSuffArr[i];
  25. }
  26.  
  27. void buildSuffArr(){
  28.     memset(suffArr,0,sizeof(suffArr)); memset(tmpSuffArr,0,sizeof(tmpSuffArr));
  29.     memset(rankk,0,sizeof(rankk)); memset(tmpRank,0,sizeof(tmpRank));
  30.     for(int i = 0; i < n; i++) rankk[i] = s[i], suffArr[i] = i;
  31.     for(int k = 1; k <= n; k<<=1){
  32.         countingSort(k);
  33.         countingSort(0);
  34.         int r = 1;
  35.         tmpRank[suffArr[0]] = r;
  36.         for(int i = 1; i < n; i++){
  37.             if(rankk[suffArr[i]]==rankk[suffArr[i-1]] && rankk[suffArr[i]+k]==rankk[suffArr[i-1]+k]) tmpRank[suffArr[i]] = r;
  38.             else tmpRank[suffArr[i]] = ++r;
  39.         }
  40.         for(int i = 0; i < n; i++) rankk[i] = tmpRank[i];
  41.     }
  42. }
  43.  
  44. void buildLcp(){
  45.     memset(pos,0,sizeof(pos)); memset(plcp,0,sizeof(plcp));
  46.     pos[suffArr[0]] = -1;
  47.     for(int i = 1; i < n; i++) pos[suffArr[i]] = suffArr[i-1];
  48.     int len = 0;
  49.     for(int i = 0; i < n; i++){
  50.         if(pos[i]==-1){
  51.             plcp[i] = 0;
  52.             continue;
  53.         }
  54.         while(s[i+len]==s[pos[i]+len]) len++;
  55.         plcp[i] = len;
  56.         len = max(len-1,0);
  57.     }
  58.     for(int i = 0; i < n; i++) lcp[i] = plcp[suffArr[i]];
  59. }
  60. set<int> st;
  61. int main() {
  62. #ifndef ONLINE_JUDGE
  63.     readFile;
  64. #endif
  65.     fastio;
  66.     scanf("%d%d",&k,&n);
  67.     scanf("%s",s);
  68.     if(k==1){
  69.         printf("%d\n",n);
  70.         return 0;
  71.     }
  72.     buildSuffArr();
  73.     buildLcp();
  74.     for(int i = 0; i < k-1; i++) st.insert(lcp[i]);
  75.     int res = *st.begin();
  76.     for(int i = k-1; i < n; i++){
  77.         st.erase(st.begin());
  78.         st.insert(lcp[i]);
  79.         res = max(res,*st.begin());
  80.     }
  81.     printf("%d\n",res);
  82.     return 0;
  83. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top