Cod sursa(job #2029892)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 30 septembrie 2017 16:51:37
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char str[200010], aux[200010];
int lsp[200010];

int main ()
{
    freopen ("pscpld.in", "r", stdin);
    freopen ("pscpld.out", "w", stdout);

    fgets (aux + 1, 100010, stdin);

    int k = strlen (aux + 1);

    int n = 0;
    str[++n] = '#';

    for (int i = 1; i < k; ++i)
        str[++n] = aux[i],
        str[++n] = '#';

    lsp[2] = 1;
    int dr = 3, poz = 2;
    for (int i = 3; i <= n; ++i)
        if (dr - i > lsp[2 * poz - i]) lsp[i] = lsp[2 * poz - i];
        else
        {
            for (++dr; dr <= n && 2 * i - dr > 0 && str[dr] == str[2 * i - dr]; ++dr);
            --dr;

            lsp[poz = i] = dr - i;
        }

    long long rez = 0LL;
    for (int i = 1; i <= n; ++i)
        rez += 1LL * (lsp[i] + 1) / 2LL;

    printf ("%lld\n", rez);

    return 0;
}