Pagini recente » Cod sursa (job #207497) | Cod sursa (job #2821824) | Cod sursa (job #44580) | Cod sursa (job #2829961) | Cod sursa (job #1674088)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N, sir[2000009], dp[2000009];
void Read ()
{
char aux[1000009];
int n;
gets (aux + 1), n = strlen (aux + 1), N = 0;
for (int i=1; i<=n; i++)
sir[++N] = '#', sir[++N] = aux[i];
sir[++N] = '#';
}
int main ()
{
freopen ("pscpld.in", "r", stdin);
freopen ("pscpld.out", "w", stdout);
Read ();
int P = 0, R = 0;
long long ToT = 0;
for (int i=1; i<=N; i++)
{
if (R >= i) dp[i] = min (R - i + 1, dp[P - (i - P)]);
while (sir[i + dp[i]] == sir[i - dp[i]] && i + dp[i] <= N && i - dp[i] >= 1) dp[i] ++;
if (i + dp[i] - 1 > R) R = i + dp[i] - 1, P = i;
if (sir[i] == '#') ToT += dp[i] / 2;
else ToT += dp[i] / 2;
}
printf ("%lld\n", ToT);
return 0;
}