Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- const unsigned int p = 29;
- unsigned int w[10001];
- long long int maxim(long long int a, long long int b)
- {
- if (a > b)
- return a;
- return b;
- }
- int main()
- {
- char s[10000];
- fgets(s, 10000, stdin);
- int i, j, len = strlen(s)-1;
- long long int max_ = len;
- unsigned int q[len+1]; //len-i+1
- w[0] = 1;
- for (int i = 1; i != len; i++)
- {
- w[i] = w[i-1] * p;
- }
- q[0] = 0;
- q[1] = 1 + s[0] - 'a';
- for (i = 2; i <= len; i++)
- {
- q[i] = q[i-1] + (s[i-1] - 'a' + 1) * w[i-1];
- }
- for (i = 1; i != len-1; i++)
- {
- unsigned int h[len - i+1];
- h[0] = q[len] - q[len-1-i];
- unsigned int t = p;
- int k = 1;
- for (j = len - i - 2; j >= 0; j--, t *= p, k++)
- {
- h[k] = (q[j+i+1] - q[j])*t;
- }
- sort(h, h+len-i);
- int ma = 1, mmm = 1;
- for (int y = 1; y < len - i; y++)
- {
- ma = 1;
- while (y != len - i && h[y] == h[y-1])
- {
- y++;
- ma++;
- }
- if (ma > mmm)
- mmm = ma;
- }
- max_ = maxim(max_, mmm*(i+1));
- /*for (int y = 0; y < len-i; y++)
- cout << h[y] << " ";
- cout << endl;*/
- }
- printf("%lld", max_);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement