Pagini recente » Cod sursa (job #3290739) | Cod sursa (job #194282) | Cod sursa (job #1055523) | Cod sursa (job #1917305) | Cod sursa (job #1876485)
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int nmx = 1000002;
char s1[nmx],s2[2*nmx];
int l[2*nmx];
long long suma;
void citire()
{
scanf("%s", s1);
int x = strlen(s1), p = 1;
s2[0] = '#';
for(int i = 0; i < x; ++i)
{
s2[p++] = s1[i];
s2[p++] = '#';
}
s2[p] = NULL;
}
void manacher()
{
int c = 0, r = 0, st, dr, x = strlen(s2);
for(int i = 1; i < x; ++i)
{
if(i > r)
{
st = i - 1;
dr = i + 1;
if(s2[i] != '#')
l[i] = 1;
}
else
{
int ii = 2 * c - i;
l[i] = min(r-i,l[ii]);
st = i - l[ii];
dr = i + l[ii];
}
while(st >= 0 && s2[st] == s2[dr])
{
if(s2[st] != '#')
l[i] += 2;
-- st;
++ dr;
}
if(i + l[i] > r)
{
r = i + l[i];
c = i;
}
suma += (l[i] + 1) / 2;
}
}
void afish()
{
/**for(int i = 0; i < strlen(s2); ++i)
printf("%c ", s2[i]);
printf("\n");
for(int i = 0; i < strlen(s2); ++i)
printf("%d ", l[i]);**/
printf("%d\n", suma);
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
citire();
manacher();
afish();
return 0;
}