Pagini recente » Cod sursa (job #1895380) | Cod sursa (job #747290) | Cod sursa (job #328734) | Cod sursa (job #795221) | Cod sursa (job #2650379)
#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 = "";
s.resize(2*rd.size() + 1);
for(int index = 0; index < rd.size(); index++)
{
s[2*index] = '|';
s[2*index + 1] = rd[index];
}
s[2*rd.size()] = '|';
//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;
}