Advertisement
Guest User

Untitled

a guest
Jul 16th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     string s; cin >> s;
  7.     int n=s.size();
  8.  
  9.     vector<vector<int>> p(2,vector<int>(n,0));
  10.     for(int z=0,l=0,r=0;z<2;z++,l=0,r=0)
  11.         for(int i=0;i<n;i++)
  12.         {
  13.             if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);
  14.             int L=i-p[z][i], R=i+p[z][i]-!z;
  15.             while(L-1>=0 && R+1<n && s[L-1]==s[R+1]) p[z][i]++,L--,R++;
  16.             if(R>r) l=L,r=R;
  17.         }
  18.  
  19.     int res=0;
  20.     for (int i=0; i<2; i++)
  21.         for(int j=0; j<n; j++)
  22.             res+=p[i][j];
  23.     cout << res;
  24. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement