Pagini recente » Cod sursa (job #1094847) | Cod sursa (job #2769170) | Cod sursa (job #804205) | Cod sursa (job #2011605) | Cod sursa (job #2761015)
#include <bits/stdc++.h>
#define nmax (int)(2e6+2)
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string a,b;
int ps[nmax];
int main()
{
f>>a;
b.push_back('&');
for(int i=0;i<a.size();i++)
{
b.push_back(a[i]);
b.push_back('&');
}
int mid=-1,k=0;
long long ans=0;
for(int i=0;i<b.size();i++)
{
if(i<=k+mid)
ps[i]=ps[2*mid-i];
while(
(i+ps[i]+1<b.size()&&i-ps[i]-1>=0)&&
b[i+ps[i]+1]==b[i-ps[i]-1]) ps[i]++;
if(ps[i]+i>mid+k)
{
mid=i;
k=ps[i];
}
// g<<ps[i]<<' '<<i<<'\n';
ans+=(long long)((ps[i]+i%2)/2);
}
g<<ans;
return 0;
}