Pagini recente » Cod sursa (job #2734371) | Cod sursa (job #1318425) | Cod sursa (job #280330) | Cod sursa (job #2271935) | Cod sursa (job #2387534)
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=1000*1000+5;
int p[2*nmax];
char s[2*nmax];
long long ans;
string ini;
int n,i,j,nr,r,c;
int main()
{
ifstream f("pscpld.in");
ofstream g("pscpld.out");
f>>ini;ans=ini.size();
s[nr++]='#';
for(i=0;i<ini.size();i++)
{
s[nr++]=ini[i];
s[nr++]='#';
}
r=c=-1;
for(i=0;i<nr;i++)
{
if(i<=r) p[i]=min(p[2*c-i],r-i);
while(i-p[i]>=0&&i+p[i]<nr&&s[i-p[i]]==s[i+p[i]])
p[i]++;
p[i]--;
if(i+p[i]>r) r=i+p[i],c=i;
ans+=1LL*p[i]/2;
}
g<<ans;
/*ifstream f("pscpld.in");
ofstream g("pscpld.out");
f>>ini;ans=ini.size();
s[nr++]='#';
for(i=0;i<ini.size();i++)
{
s[nr++]=ini[i];
s[nr++]='#';
}
r=c=-1;
for(i=0;i<nr;i++)
{
if(i<=r) p[i]=min(p[2*c-i],r-i);
while(i-p[i]>=0&&i+p[i]<nr&&s[i-p[i]]==s[i+p[i]])
p[i]++;
p[i]--;
if(i+p[i]>r) r=i+p[i],c=i;
ans+=1LL*p[i]/2;
}
g<<ans;*/
return 0;
}