Pagini recente » Cod sursa (job #3252090) | Cod sursa (job #198960) | Cod sursa (job #2845403) | Cod sursa (job #1179610) | Cod sursa (job #3186884)
#include<fstream>
std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");
std::string s;
int vec[2500000];
long long size;
void precalc()
{
fin>>s;
size=s.size();
for(int index=0; index<size; ++index)
{
s.insert(s.begin()+index,'#');
++size;
++index;
}
s.insert(s.end(), '#');
++size;
}
void manacher()
{
int c=0, r=0;
for(int index=0; index<size; ++index)
{
int sim=2*c-index;
vec[index]=std::max(0, std::min(vec[sim], r-index));
while(s[index+vec[index]]==s[index-vec[index]] && index+vec[index]<size && index-vec[index]>=0)
++vec[index];
if(index+vec[index]>r)
{
r=index+vec[index];
c=index;
}
}
}
bool isLetter(char x)
{
return x>='a' && x<='z';
}
void getTotal()
{
int ans=0;
for(int index=0; index<size; ++index)
{
if(isLetter(s[index]))
while(vec[index]>0)
{
++ans;
vec[index]-=2;
}
else
while(vec[index]>1)
{
++ans;
vec[index]-=2;
}
}
fout<<ans;
}
int main()
{
precalc();
manacher();
getTotal();
return 0;
}