Pagini recente » Cod sursa (job #2850257) | Cod sursa (job #986184) | Cod sursa (job #2929003) | Cod sursa (job #809378) | Cod sursa (job #975593)
Cod sursa(job #975593)
#include <cstring>
#include <fstream>
using namespace std;
char str[1000002], s[2000006];
int p[2000006], i, len, n, l, r;
long long nr=1;
void expand(int &l, int &r)
{
while(s[l-1]==s[r+1] && l>=2 && r<=n-1)
++p[i], --l, ++r;
}
void manacher()
{
len=strlen(str)-1;
for(i=0;i<=len;++i)
{
s[++n]=str[i];
s[++n]='#';
}
l=r=1;
for(i=2;i<=n;++i)
{
if(i<=r)
{
p[i]=min(p[r-i+l], r-i);
if(p[i]==r-i)
{
l=i-p[i];
expand(l, r);
}
}
else
{
r=l=i;
expand(l, r);
}
if(i&1)
nr+=(p[i]+2)>>1;
else
nr+=(p[i]+1)>>1;
}
}
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin>>str;
manacher();
fout<<nr<<'\n';
return 0;
}