Pagini recente » Cod sursa (job #152561) | Cod sursa (job #1964517) | Cod sursa (job #2414780) | Borderou de evaluare (job #1036140) | Cod sursa (job #3263614)
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int manacher[1000001];
int main()
{
int i,sum=0,best;
string s,aux;
cin>>aux;
for(i=0;i<aux.size();i++){
s+='$';s+=aux[i];
}s+='$';
best=-1;
for(i=0;i<s.size();i++){
if(best!=-1 && best+manacher[best]-1>=i){
manacher[i]=min(best+manacher[best]-i,manacher[2*best-i]);
}
while(i+manacher[i]<s.size() && i-manacher[i]>=0 && s[i+manacher[i]]==s[i-manacher[i]])
manacher[i]++;
if(best==-1 || i+manacher[i]-1>best+manacher[best]-1)
best=i;
}
for(i=0;i<s.size();i++){
if(manacher[i]){
sum+=manacher[i]/2;
}
}
cout<<sum;
return 0;
}