daily pastebin goal
81%
SHARE
TWEET

Untitled

a guest Sep 26th, 2014 1,756 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
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