Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int main() {
- string s; cin >> s;
- int n=s.size();
- vector<vector<int>> p(2,vector<int>(n,0));
- for(int z=0,l=0,r=0;z<2;z++,l=0,r=0)
- for(int i=0;i<n;i++)
- {
- if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);
- int L=i-p[z][i], R=i+p[z][i]-!z;
- while(L-1>=0 && R+1<n && s[L-1]==s[R+1]) p[z][i]++,L--,R++;
- if(R>r) l=L,r=R;
- }
- int res=0;
- for (int i=0; i<2; i++)
- for(int j=0; j<n; j++)
- res+=p[i][j];
- cout << res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement