Pagini recente » Cod sursa (job #1901734) | Cod sursa (job #2402313) | Cod sursa (job #2941069) | Cod sursa (job #911386) | Cod sursa (job #2868286)
#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];
}
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 (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';
}