Pagini recente » Cod sursa (job #190371) | Cod sursa (job #2752114) | Cod sursa (job #1197339) | Cod sursa (job #3286341) | Cod sursa (job #3187051)
#include<fstream>
std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");
std::string initial;
char s[2000005];
int vec[2000005];
long long size;
inline void precalc()
{
fin>>initial;
int aux=initial.size();
for(int index=0; index<aux; ++index)
{
s[size++]='#';
s[size++]=initial[index];
}
s[size++]='#';
s[size]='\0';
}
inline void manacher()
{
long long ans=0;
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(index+vec[index]<=size && index-vec[index]>=0 && s[index+vec[index]]==s[index-vec[index]])
++vec[index];
--vec[index];
ans+=(vec[index]+1)/2;
if(index+vec[index]>r)
{
r=index+vec[index];
c=index;
}
}
fout<<ans;
}
int main()
{
std::ios_base::sync_with_stdio(false);
precalc();
manacher();
return 0;
}