Pagini recente » Cod sursa (job #3040522) | Cod sursa (job #1074201) | Cod sursa (job #1117901) | Cod sursa (job #3133902) | Cod sursa (job #3290907)
#ifndef LOCAL
#pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#endif
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;
using namespace std;
/*******************************/
// INPUT / OUTPUT
#ifndef LOCAL
ifstream in("pscpld.in");
ofstream out("pscpld.out");
#define cin in
#define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS
string s;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
cin >> s;
}
///-------------------------------------
inline string get_manacher_string(string s)
{
string nou = "!";
for (int i = 0 ; i < s.length() - 1 ; ++ i)
{
nou += s[i];
nou += "#";
}
nou += s[s.length() - 1];
nou += ".";
return nou;
}
///-------------------------------------
inline vector <int> get_manacher(string s)
{
int N = s.length();
vector <int> m(N, 0);
m[0] = 1;
while (m[1] + 1 < N && 1 - m[1] >= 0 && s[m[1] + 1] == s[1 - m[1]]) m[1] ++;
int mij = 1, capat_dr = 1 + m[1];
for (int i = 2 ; i < N ; ++ i)
{
m[i] = min(m[mij - (i - mij)], capat_dr - i);
while (i + m[i] < N && i - m[i] >= 0 && s[m[i] + i] == s[i - m[i]]) m[i] ++;
if (i + m[i] > capat_dr)
{
mij = i;
capat_dr = i + m[i];
}
}
return m;
}
///-------------------------------------
inline int get_palindrome_count(vector <int> m)
{
int cnt = 0;
for (int i = 0 ; i < m.size() ; ++ i)
{
if (i % 2 == 0) cnt += m[i] / 2;
else cnt += (m[i] + 1) / 2;
}
return cnt;
}
///-------------------------------------
inline void Solution()
{
s = get_manacher_string(s);
auto m = get_manacher(s);
cout << get_palindrome_count(m);
}
///-------------------------------------
inline void Output()
{
}
///-------------------------------------
signed main()
{
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
ReadInput();
Solution();
Output();
return 0;
}