Pagini recente » Cod sursa (job #550727) | Cod sursa (job #2970659) | Cod sursa (job #2845118) | Cod sursa (job #1104601) | Cod sursa (job #2761024)
#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]>mid+k-i?mid+k-i:ps[2*mid-i];
//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;
}