Pagini recente » Cod sursa (job #2515635) | Cod sursa (job #2523860) | Cod sursa (job #2482370) | Cod sursa (job #2483300) | Cod sursa (job #2841458)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
long long manacher(string s)
{
string a="@#";
for(char c:s)
a+=c+string("#");
a+='$';
int l=0,r=-1;
int n=a.size()-2;
vector<int> p(n+2);
for(int i=1;i<=n;++i)
{
p[i]=max(0,min(r-i,p[l+r-i]));
while(a[i-p[i]]==a[i+p[i]])
++p[i];
if(i+p[i]>r)
l=i-p[i],r=i+p[i];
}
long long ans=0;
for(int i=2;i<p.size()-2;++i)
ans+=p[i]/2;
return ans;
}
string s;
int main()
{
ios_base::sync_with_stdio(false);
in.tie(0),out.tie(0);
in>>s;
out<<manacher(s)<<'\n';
return 0;
}