Pagini recente » Cod sursa (job #33589) | Cod sursa (job #570427) | Cod sursa (job #2039865) | Cod sursa (job #2382862) | Cod sursa (job #1281632)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char s[2000005];
int v[2000005],imax,lgmax;
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n,i;
long long sol=0;
fin>>s;
n=strlen(s);
for(i=n-1;i>=0;--i)
s[i*2+1]=s[i];
n=2*n;
s[0]='$';
s[n+1]='&';
for(i=2;i<=n;i+=2)
s[i]='#';
v[1]=1;
imax=1;
lgmax=1;
for(i=1;i<=n;++i)
{
v[i]=min(imax+lgmax-i,v[2*imax-i]);
while(s[i-v[i]]==s[i+v[i]])
v[i]++;
if(i+v[i]>imax+lgmax)
imax=i,lgmax=v[i];
}
for(i=1;i<=n;++i)
if(i%2==1)
sol+=(v[i]+1)/2;
else
sol+=v[i]/2;
fout<<sol;
return 0;
}