Pagini recente » Cod sursa (job #1934494) | Cod sursa (job #1575258) | Cod sursa (job #1949245) | Cod sursa (job #1202952) | Cod sursa (job #1975063)
#include <cstring>
#include <fstream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int palindromeCreation(string& S) {
vector<char> aux;
vector<int>Manacher;
aux.push_back('*');
for(int i=0;i<S.size();i++)
{
aux.push_back(S[i]);
aux.push_back('*');
}
Manacher.push_back(0);
int r=0,c=0;
for(int i=1;i<aux.size();i++)
{
if(i<=r)
{
int a=2*c-i;
int len=min(Manacher[a],r-i);
if(i+len==r)
while(i-len-1>=0&&i+len+1<aux.size()&&aux[i+len+1]==aux[i-len-1])
r++,len++,c=i;
Manacher.push_back(len);
}
else
{
int l=0;
c=i,r=i;
while(i-l-1>=0&&i+l+1<aux.size()&&aux[i-l-1]==aux[i+l+1])
l++,r++;
Manacher.push_back(l);
}
}
long long ans=0;
for(int i=0;i<aux.size();i++)
ans+=1LL*(Manacher[i]+1)/2;
return ans;
}
int main() {
string S;
in >> S;
out << palindromeCreation(S) << "\n";
return 0;
}