Pagini recente » Cod sursa (job #1013622) | Cod sursa (job #2699560) | Cod sursa (job #2835889) | Cod sursa (job #847682) | Cod sursa (job #1125401)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
#include <cstring>
#define ll long long
#define LE 2000666
#define cout g
string s,S;
int i,pal[LE];
int main()
{
getline(f,s);
S+="X ";
int N=s.length();
for(i=0; i<N; ++i)
{
S+=s[i];
S+=" ";
}
S+="W";
N=S.length();
int st=-1,dr=-1;
for(i=1; i<N-1; ++i)
{
if (i>=st&&i<=dr)
{
int C=(st+dr)/2;
pal[i]=min(dr-i+1,pal[C-(i-C)]);
}
while (S[i+pal[i]]==S[i-pal[i]]) ++pal[i];
if (i+pal[i]-1>dr) st=i-pal[i]+1,dr=i+pal[i]-1;
}
ll result=0;
for(i=1;i<N-1;++i)
{
result+=(ll)pal[i]/(ll)2;
if (S[i]!=' '&&pal[i]%2) ++result;
}
// cout<<S;
// cout<<'\n';
// for(i=0;i<N;++i) cout<<pal[i]<<" ";
// cout<<'\n';
cout<<result<<'\n';
return 0;
}