Pagini recente » Cod sursa (job #1716330) | Cod sursa (job #1652661) | Cod sursa (job #1584326) | Cod sursa (job #295699) | Cod sursa (job #1880258)
#include <cstdio>
#include <cstring>
#define Cmax 1000002
using namespace std;
char sentence[Cmax];
int lps[2*Cmax + 1],c,r,dif;
long long nr;
void read()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",&sentence);
}
void manacher()
{
lps[0]= 0;
lps[1]= 1;
c = 1;
r = 2;
int lung = strlen(sentence);
int simetric;
lung = lung * 2 + 1;
for(int i = 2 ; i < lung; i++)
{
dif = r - i;
simetric = 2*c-i;
if(i < r)
{
if( lps[simetric] < dif)
lps[i] = lps[simetric];
else
lps[i] = dif;
}
else
lps[i] = 0;
while((i - lps[i]-1 >= 0 && i + lps[i] + 1 <= lung) && ((sentence[(i-lps[i]-1)/2] == sentence[(i + lps[i]+1)/2]) || ((1+lps[i]+i)%2 == 0 )))
lps[i]++;
if(lps[i] + i > r)
{
c = i;
r = i + lps[i];
}
}
for(int i = 1 ; i < lung - 1 ; i++)
if(lps[i] % 2 == 0)
nr+= lps[i] / 2;
else
nr+= lps[i]/2 + 1;
}
int main()
{
read();
manacher();
printf("%lld",nr);
return 0;
}