Pagini recente » Cod sursa (job #69420) | Cod sursa (job #1357911) | Cod sursa (job #590478) | Cod sursa (job #2572759) | Cod sursa (job #2650377)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int NMAX = 1000007;
string rd;
vector<int> pal_array(string s)
{
int n = s.size();
s = "@" + s + "$";
vector<int> len(n + 1);
int l = 1, r = 1;
for(int i = 1; i <= n; i++)
{
len[i] = min(r - i, len[l + (r - i)]);
while(s[i - len[i]] == s[i + len[i]])
len[i]++;
if(i + len[i] > r)
{
l = i - len[i];
r = i + len[i];
}
}
len.erase(begin(len));
return len;
}
int main()
{
in >> rd;
string s = "";
for(auto ch : rd)
{
s = (s + '|') + ch;
}
s = s + '|';
//out << s << endl;
auto p = pal_array(s);
long long sum = 0;
for(int i = 0; i < p.size(); i++)
{
//out << p[i] << " ";
if(i%2 == 1)
{
sum += (p[i]+1)/2;
}
else
{
sum += (p[i])/2;
}
}
out << sum;
}