Cod sursa(job #1674088)

Utilizator geniucosOncescu Costin geniucos Data 4 aprilie 2016 13:04:43
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#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;
}