Pagini recente » Cod sursa (job #1589632) | Cod sursa (job #2099347) | Cod sursa (job #1860046) | Cod sursa (job #1383280) | Cod sursa (job #2634824)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int manacher[2000006];//retinem cat de mult ne putem duce in dreapta
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s,inits;
fin >> inits;
s="&&";
for(auto x:inits)
{
s+=x;
s+="&";
}
int mid=0;
for(int i=1; i<s.size(); ++i)
{
if(mid + manacher[mid] >= i)//i se afla in interiorul palindromului
{
manacher[i]=min(manacher[mid-(i-mid)],mid + manacher[mid] - i);
while(i + manacher[i] + 1 < s.size() and i - manacher[i] - 1 >=1 and s[i+manacher[i]+1]== s[i - manacher[i]-1])
manacher[i]+=1;
if(i + manacher[i] >= mid + manacher[mid])
mid=i;
}
else
{
manacher[i]=0;
while(i+manacher[i]+1 < s.size() and i-manacher[i]-1>=1 and s[i+manacher[i]+1]== s[i-manacher[i]-1])
manacher[i]+=1;
mid=i;
}
}
long long ans=0;
for(int i=1; i<s.size(); ++i)
ans+=(manacher[i] + 1)/2;
fout<<ans;
return 0;
}