Pagini recente » Cod sursa (job #1790615) | Cod sursa (job #1692123) | Cod sursa (job #1124262) | Cod sursa (job #2054221) | Cod sursa (job #2868296)
#include <bits/stdc++.h>
using namespace std;
//const int dim = 2002;
ifstream fin ("pscpld.in");
ofstream fout("pscpld.out");
int lg[2000004];
int main()
{
string a,s;
fin>>a;
int n=a.size();
for (int i=0;i<n;i++)
{
s+='$';
s+=a[i];
}
s+='$';
int c=0,dr=0;
lg[0]=1;
for (int i=1;i<2*n+1;i++)
{
int ogl=2*c-i;
lg[i]=min(lg[ogl], dr-i);
while (i+lg[i]+1<2*n+1 && i-lg[i]-1>0 && s[i+lg[i]+1]==s[i-lg[i]-1])
lg[i]++;
if (i+lg[i]>dr)
{
dr=i+lg[i];
c=i;
}
}
long long sol=n;
for (int i=1;i<2*n+1;i++)
{
lg[i]/=2;
sol+=lg[i];
}
fout<<sol<<'\n';
}