Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <string>
- #include <vector>
- #include <iostream>
- using namespace std;
- int main()
- {
- string s;
- cin >> s;
- {
- vector<char> t;
- t.push_back(' ');
- for(char c:s)
- {
- t.push_back(c);
- t.push_back(' ');
- }
- s= string(t.begin(),t.end());
- }
- int n= (int)s.size();
- vector<int> ro(n, 1);
- int left=0,right=0;
- for(int i=1; i<n; i++)
- {
- int L,R;
- if(i > right)
- {
- L = i;
- R = i;
- }
- else
- {
- int mi= right+left-i;
- L= i-ro[mi]+1;
- R= i+ro[mi]-1;
- if(R > right)
- {
- int d= R-right;
- R = R-d;
- L = L+d;
- }
- }
- while(L-1>=0 && R+1<n && s[L-1] == s[R+1])
- {
- L--; R++;
- }
- ro[i] = R-i+1;
- if(R > right)
- {
- left = L;
- right = R;
- }
- }
- long long c = 0;
- for(int &value:ro) c += value/2;
- cout << c;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement