Advertisement
Guest User

Untitled

a guest
Nov 19th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 1.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const unsigned int p = 29;
  7. unsigned int w[10001];
  8.  
  9. long long int maxim(long long int a, long long int b)
  10. {
  11.     if (a > b)
  12.         return a;
  13.     return b;
  14. }
  15.  
  16. int main()
  17. {
  18.     char s[10000];
  19.     fgets(s, 10000, stdin);
  20.     int i, j, len = strlen(s)-1;
  21.     long long int max_ = len;
  22.     unsigned int q[len+1];   //len-i+1
  23.     w[0] = 1;
  24.     for (int i = 1; i != len; i++)
  25.     {
  26.         w[i] = w[i-1] * p;
  27.     }
  28.     q[0] = 0;
  29.     q[1] = 1 + s[0] - 'a';
  30.     for (i = 2; i <= len; i++)
  31.     {
  32.         q[i] = q[i-1] + (s[i-1] - 'a' + 1) * w[i-1];
  33.     }
  34.     for (i = 1; i != len-1; i++)
  35.     {
  36.         unsigned int h[len - i+1];
  37.         h[0] = q[len] - q[len-1-i];
  38.         unsigned int t = p;
  39.         int k = 1;
  40.         for (j = len - i - 2; j >= 0; j--, t *= p, k++)
  41.         {
  42.             h[k] = (q[j+i+1] - q[j])*t;
  43.         }
  44.         sort(h, h+len-i);
  45.         int ma = 1, mmm = 1;
  46.         for (int y = 1; y < len - i; y++)
  47.         {
  48.             ma = 1;
  49.             while (y != len - i && h[y] == h[y-1])
  50.             {
  51.                 y++;
  52.                 ma++;
  53.             }
  54.             if (ma > mmm)
  55.                 mmm = ma;
  56.         }
  57.  
  58.  
  59.         max_ = maxim(max_, mmm*(i+1));
  60.  
  61.         /*for (int y = 0; y < len-i; y++)
  62.             cout << h[y] << " ";
  63.         cout << endl;*/
  64.     }
  65.  
  66.     printf("%lld", max_);
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement