Pagini recente » Cod sursa (job #2393768) | Cod sursa (job #2489260) | Cod sursa (job #403285) | Cod sursa (job #660381) | Cod sursa (job #1693451)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1000002
using namespace std;
int n, i, j, pos, a;
long long sol;
int len[maxN * 2];
char s[maxN * 2], S[maxN];
void read()
{
freopen("pscpld.in", "r", stdin);
gets(S + 1);
n=strlen(S + 1);
s[0]='*';
for (i=1;i<=n;++i)
{
s[(i-1)*2+1]=S[i];
s[i*2]='*';
}
n*=2;
}
void solve()
{
pos=0;
a=0;
sol=0;
for (i=1;i<=n;++i)
{
if (i<=pos)
len[i]=min(len[2*a-i],(pos - i));
while (i-len[i]-1>=0 && i+len[i]+1<=n && s[i-len[i]-1]==s[i+len[i]+1])
++len[i];
if (i+len[i]>pos)
{
pos=i+len[i];
a=i;
}
sol=(long long)(sol+(len[i]+1)/2)*1LL;
}
}
void write()
{
freopen("pscpld.out","w",stdout);
printf("%lld\n",sol);
}
int main()
{
read();
solve();
write();
return 0;
}