Pagini recente » Cod sursa (job #232068) | Cod sursa (job #1662795) | Cod sursa (job #1386170) | Cod sursa (job #2721240) | Cod sursa (job #1174145)
#include <fstream>
#include <cstring>
using namespace std;
#define NMax 1000050
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char S[NMax];
int n;
int Pi[NMax],Pp[NMax];
unsigned long long sol;
int main()
{
int i;
S[0]='a'-1;
f.get((S+1),503);
n=strlen(S)-1;
S[n+2]='\0';
S[n+1]='a'-2;
int L,R,C,p,d;
L=R=C=0;
//palindrom impar
for(i=1;i<=n;i++)
{
if(i>R)
{
p=1;
while(S[i-p]==S[i+p] && S[i-p+1]>=S[i-p] && S[i+p-1]>=S[i+p]) p++;
p--;
Pi[i]=(p<<1)|1;
L=i-p,R=i+p,C=i;
}
else
{
d=i-C;
if(C-d-Pi[C-d]/2<L) p=C-d-L+1;
else p=Pi[C-d]/2+1;
while(S[i-p]==S[i+p] && S[i-p+1]>=S[i-p] && S[i+p-1]>=S[i+p]) p++;
p--;
Pi[i]=(p<<1)|1;
if(i+Pi[i]/2>R) L=i-p,R=i+p,C=i;
}
}
L=R=C=0;
//palindrom par
for(i=1;i<=n;i++)
{
if(i>R)
{
if(S[i]==S[i+1])
{
p=1;
while(S[i-p]==S[i+1+p] && S[i-p+1]>=S[i-p] && S[i+p]>=S[i+p+1]) p++;
Pp[i]=(p<<1);
Pp[++i]=(p<<1);
L=i-p+1,R=i+p,C=i;
} else L=i,R=i,C=i;
}
else if(S[i]==S[i+1])
{
d=i-C-1;
if(C-d-Pp[C-d]/2<L) p=C-d-L;
else p=Pp[C-d]/2;
while(S[i-p]==S[i+1+p] && S[i-p+1]>=S[i-p] && S[i+p]>=S[i+p+1]) p++;
Pp[i]=(p<<1);
Pp[++i]=(p<<1);
if(i+Pi[i]/2>R) L=i-p+1,R=i+p,C=i;
}
}
for(i=1;i<=n;i++)
{
sol+=(unsigned long long)((Pi[i]+1)/2+Pp[i]/2);
}
g<<sol<<"\n";
f.close();
g.close();
return 0;
}