Pagini recente » Cod sursa (job #3317911) | Cod sursa (job #3302554) | Cod sursa (job #3317912) | Cod sursa (job #3305257) | Cod sursa (job #3305881)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int manacher[1000001];
int main()
{
string a,s;
fin>>a;
s="##";
for(int i=0;i<a.size();i++)
{
s+=a[i];
s+='#';
}
int best=0;
for(int i=1;i<s.size();i++)
{
if(best+manacher[best]>=i)
{
manacher[i]=min(manacher[best-(i-best)],best+manacher[best]-i);
while(i+manacher[i]+1<s.size() && i-manacher[i]-1>=1 && s[i+manacher[i]+1]==s[i-manacher[i]-1])
{
manacher[i]++;
}
if(i+manacher[i]>=best+manacher[best])
{
best=i;
}
}
else
{
manacher[i]=0;
while(i+manacher[i]+1<s.size() && i-manacher[i]-1>=1 && s[i+manacher[i]+1]==s[i-manacher[i]-1])
{
manacher[i]++;
}
best=i;
}
}
long long ans=0;
for(int i=1;i<s.size();i++)
{
ans+=(manacher[i]+1)/2;
}
fout<<ans;
return 0;
}