Pagini recente » Cod sursa (job #364363) | Cod sursa (job #1020576) | Cod sursa (job #1798420) | Monitorul de evaluare | Cod sursa (job #297369)
Cod sursa(job #297369)
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "pscpld.in"
#define FOUT "pscpld.out"
#define MAX_N 1000005
char A[MAX_N];
int P[MAX_N << 1];
int N;
inline int ok (int c1, int c2, int let)
{
if (c1 - let > 0 && c2 + let <= N) return 1;
return 0;
}
void solve ()
{
int i, c, mex, mirr, mex_i, let, c1, c2, dif;
// initializari
P[1] = 1;
mex = 1, mex_i = 1;
for (i = 2; i <= N << 1; ++i)
if (i & 1)
{
P[i] = 1;
dif = i - mex_i;
if (i <= mex)
mirr = mex_i - dif;
else
mirr = i;
P[i] = P[mirr], let = P[mirr] / 2;
c1 = c2 = (i + 1) >> 1;
++let;
while (A[c1 - let] == A[c2 + let] && ok (c1, c2, let)) ++let, P[i] += 2;
--let;
int nm = ((c2 + let) << 1) - 1;
if (nm > mex) mex = nm, mex_i = i;
}
else
{
dif = i - mex_i;
if (i <= mex)
mirr = mex_i - dif;
else
mirr = i;
P[i] = P[mirr], let = P[mirr] / 2 - 1;
c1 = i >> 1, c2 = c1 + 1;
++let;
while (A[c1 - let] == A[c2 + let] && ok (c1, c2, let)) ++let, P[i] += 2;
--let;
int nm = ((c2 + let) << 1) - 1;
if (nm > mex) mex = nm, mex_i = i;
}
long long BEST = 0;
for (i = 1; i <= N << 1; ++i)
{
if (!P[i]) continue;
if (P[i] == 1)
{
++BEST;
continue;
}
if (i & 1) BEST += (P[i]/2 + 1);
else BEST += P[i]/2;
}
printf ("%lld\n", BEST);
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
gets (A + 1);
N = strlen (A + 1);
solve ();
return 0;
}