Pagini recente » Cod sursa (job #1482474) | Cod sursa (job #2283815) | Cod sursa (job #487819) | Cod sursa (job #216630) | Cod sursa (job #916722)
Cod sursa(job #916722)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define NMAX 2000005
char s[NMAX],t[NMAX];
int p[NMAX],n;
void compute_t()
{
int i;
t[0]='1';
for(i=1;i<=n;i++) {
t[2*i-1]='#';
t[2*i]=s[i];
}
t[2*n+1]='#';
t[2*n+2]='2';
n=2*n+2;
}
void manacher()
{
int R,C,i,j;
compute_t();
R=1;
C=1;
for(i=2;i<=n-1;i++) {
j=2*C-i;
if(i+p[j]<R)
p[i]=p[j];
else {
p[i]=R-i;
while(t[i+p[i]+1]==t[i-p[i]-1])
p[i]++;
}
if(i+p[i]>R) {
R=p[i]+i;
C=i;
}
}
}
int main ()
{
int i;
long long nr;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
f>>(s+1);
f.close();
n=strlen(s+1);
manacher();
nr=0;
for(i=1;i<=n-1;i++)
nr=0LL+nr+p[i]/2+1;
g<<nr-(n-2)/2-1;
g.close();
return 0;
}