Pagini recente » Cod sursa (job #3211352) | Cod sursa (job #2884438) | Cod sursa (job #1023029) | Cod sursa (job #1123369) | Cod sursa (job #2954136)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int nmax = 1e6;
int manacher[2*nmax+3];
int st,dr,n,r;
long long sol=1;
string cuv;
char s[2*nmax+3];
int main()
{
fin>>cuv;
n=cuv.length();
for(int i=0; i<2*n; i++)
{
if(i%2==0) s[i]='#';
else s[i]=cuv[i/2];
}
manacher[1]=1;
st=1;
dr=2;
for(int i=2; i<2*n; i++)
{
r = min( manacher[st-(i-st)], max(dr-i,0)) ;
while(i+r<2*n && i>r && s[i+r+1] == s[i-r-1])
{
r++;
}
if(i+r>dr) st=i, dr=i+r;
manacher[i]=r;
if(i%2==1)
{
sol+=r/2;
}
else sol+=(r+1)/2 + 1;
}
// cout<<s<<"\n";
// for(int i=0; i<2*n; i++) cout<<manacher[i];
// cout<<"\n";
fout<<sol;
}