Advertisement
Guest User

Untitled

a guest
Sep 26th, 2014
3,520
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <string>
  5. #include <cstdio>
  6. using namespace std;
  7.  
  8. const int maxn = 10100100;
  9.  
  10. int len[maxn];
  11. int suffLink[maxn];
  12. int to[maxn][2];
  13. int cnt[maxn];
  14. int numV;
  15. char str[maxn];
  16.  
  17. int v;
  18.  
  19. void addLetter(int n)
  20. {
  21.     while (str[n - len[v] - 1] != str[n] )
  22.         v = suffLink[v];
  23.     int u = suffLink[v];
  24.     while (str[n - len[u] - 1] != str[n] )
  25.         u = suffLink[u];
  26.     int u_ = to[u][str[n] - 'a'];
  27.     int v_ = to[v][str[n] - 'a'];
  28.     if (v_ == -1)
  29.     {
  30.         v_ = to[v][str[n] - 'a'] = numV;
  31.         len[numV++] = len[v] + 2;
  32.         suffLink[v_] = u_;
  33.     }
  34.     v = v_;
  35.     cnt[v]++;
  36. }
  37.  
  38. void init()
  39. {
  40.     memset(to, -1, sizeof to);
  41.     str[0] = '#';
  42.     len[0] = -1;
  43.     len[1] = 0;
  44.     len[2] = len[3] = 1;
  45.     suffLink[1] = 0;
  46.     suffLink[0] = 0;
  47.     suffLink[2] = 1;
  48.     suffLink[3] = 1;
  49.     to[0][0] = 2;
  50.     to[0][1] = 3;
  51.     numV = 4;  
  52. }
  53.  
  54. int main()
  55. {
  56.     init();
  57.     scanf("%s", str + 1);
  58.     int n = strlen(str);
  59.     for (int i = 1; i < n; i++)
  60.         addLetter(i);
  61.  
  62.     long long ans = 0;
  63.     for (int i = numV - 1; i > 0; i--)
  64.     {
  65.         cnt[suffLink[i] ] += cnt[i];
  66.         ans = max(ans, cnt[i] * 1LL * len[i] );
  67. //      fprintf(stderr, "i = %d, cnt = %d, len = %d\n", i, cnt[i], len[i] );
  68.     }
  69.     printf("%lld\n", ans);
  70.  
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement