Pagini recente » Cod sursa (job #2244381) | Cod sursa (job #340401) | Cod sursa (job #1597969) | Cod sursa (job #758327) | Cod sursa (job #2510631)
#include <fstream>
#define N 1000004
#include <cstring>
using namespace std;
char ch[2*N],s[N];
int lp[2*N];
int main()
{
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n,c,lg,exp,dr,i,ii;
f>>ch;
n=strlen(ch);
lg=-1;
for( i=0;i<n;++i)
{
s[++lg]='!';
s[++lg]=ch[i];
}
s[++lg]='!';
long long ss=n;
c=1,dr=2;
lp[1]=1;
for(i=2;i<=lg;++i)
{
ii=c-(i-c);
exp=0;
if(dr<=i)
exp=1;
else
{
if(lp[ii]<dr-i)///se gaseste in palindromul mare, dar nu e prefix
lp[i]=lp[ii];
else
if(lp[ii]==dr-i)///e prefix al palindromului mare
lp[i]=lp[ii],exp=1;
else
if(lp[ii]>dr-i)///se afla in exteriorul palindromului
lp[i]=dr-i,exp=1;
}
if(exp)
{
while(i-lp[i]-1>=0 && i+lp[i]+1<=lg)
if((i-lp[i])%2!=0)
++lp[i];
else
if(s[i-lp[i]-1]==s[i+lp[i]+1])
++lp[i];
else
break;
}
if(dr<i+lp[i])
dr=i+lp[i],c=i;
ss=ss+(long long)lp[i]/2;
}
g<<ss<<'\n';
f.close();
g.close();
return 0;
}