Pagini recente » Cod sursa (job #558739) | Cod sursa (job #2608972) | Cod sursa (job #3176747) | Cod sursa (job #2853872) | Cod sursa (job #2026971)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream si("pscpld.in");
ofstream so("pscpld.out");
char a[2000005];
char t[2000005];
int lg[2000005];
void manacher(int n)
{
int r=-1,c=0,rad;
for(int i=0;i<n;++i)
{
if(i<=r)
rad=min(lg[2*c-i],r-i)+1;
else
rad=0;
while(i-rad>=0&&i+rad<n&&a[i-rad]==a[i+rad])
++rad;
lg[i]=rad-1;
if(i+lg[i]-1>r)
{
c=i;
r=i+lg[i]-1;
}
}
}
int main()
{
si>>t;
int n;
n=strlen(t);
for(int i=0;i<=n;++i)
{
a[i*2]='#';
a[i*2+1]=t[i];
}
n=n*2+1;
manacher(n);
long long rasp=0;
for(int i=0;i<n;++i)
{
rasp+=(1LL*(lg[i]+1))/2;
}
so<<rasp;
return 0;
}