SHARE
TWEET

Untitled

a guest Nov 7th, 2018 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <string>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6. int main()
  7. {
  8.     string s;
  9.     cin >> s;
  10.     {
  11.         vector<char> t;
  12.         t.push_back(' ');
  13.         for(char c:s)
  14.         {
  15.             t.push_back(c);
  16.             t.push_back(' ');
  17.         }
  18.         s= string(t.begin(),t.end());
  19.     }
  20.     int n= (int)s.size();
  21.     vector<int> ro(n, 1);
  22.     int left=0,right=0;
  23.     for(int i=1; i<n; i++)
  24.     {
  25.         int L,R;
  26.         if(i > right)
  27.         {
  28.             L = i;
  29.             R = i;
  30.         }
  31.         else
  32.         {
  33.             int mi= right+left-i;
  34.             L= i-ro[mi]+1;
  35.             R= i+ro[mi]-1;
  36.             if(R > right)
  37.             {
  38.                 int d= R-right;
  39.                 R = R-d;
  40.                 L = L+d;
  41.             }
  42.         }
  43.         while(L-1>=0 && R+1<n && s[L-1] == s[R+1])
  44.         {
  45.             L--; R++;
  46.         }
  47.         ro[i] = R-i+1;
  48.         if(R > right)
  49.         {
  50.             left = L;
  51.             right = R;
  52.         }
  53.     }
  54.     long long c = 0;
  55.     for(int &value:ro) c += value/2;
  56.     cout << c;
  57.     return 0;
  58. }
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