Pagini recente » Cod sursa (job #512973) | Cod sursa (job #2178152) | aabbbaaa | Cod sursa (job #1596018) | Cod sursa (job #2785839)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
void pal()
{
int n=s.size();
if(n==0)
return;
n=2*n+1;
int l[n];
l[0]=0;
l[1]=1;
int c=1;
int r=2;
int i=0;
int imirror;
int maxl=1;
int maxc=0;
int start=-1;
int end=-1;
int diff=-1;
for(i=2; i<n; i++)
{
imirror=2*c-i;
l[i]=0;
diff=r-i;
if(diff>0)
l[i]=min(l[imirror],diff);
while(((i+l[i])<n&&(i-l[i])>0)&&
(((i+l[i]+1)%2==0)||
(s[(i+l[i]+1)/2]==s[(i-l[i]-1)/2])))
{
l[i]++;
}
if(l[i]>maxl)
{
maxl=l[i];
maxc=i;
}
if(i+l[i]>r)
{
c=i;
r=i+l[i];
}
}
long long sum=0;
for(i=0; i<n; i++)
{//fout<<(l[i]+1)/2<<'\n';
sum+=(l[i]+1)/2;
}
fout<<sum;
}
int main()
{
fin>>s;
pal();
return 0;
}