Pagini recente » Cod sursa (job #670554) | Cod sursa (job #631954) | Cod sursa (job #274620) | Cod sursa (job #2279357) | Cod sursa (job #3292830)
#include <bits/stdc++.h>
using namespace std;
string s,suport="";
int L[2000005];
long long manacher()
{
long long best=0,ans=0;
for(int i=1; i<suport.size()-1; i++)
{
int rightBound=best+L[best];
if(rightBound>i)
L[i]=min(rightBound-i, L[2*best-i]);
while(i+L[i]+1<suport.size() && i-L[i]-1>=0 && suport[i+L[i]+1]==suport[i-L[i]-1])
L[i]++;
if(i+L[i]>rightBound)
best=i;
ans+=(L[i]+1)/2;
}
return ans;
}
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
cin>>s;
suport+='#';
for(int i=0; i<s.size(); i++)
suport+=s[i], suport+='#';
cout<<manacher();
return 0;
}