Cod sursa(job #1873736)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 9 februarie 2017 13:02:29
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 1000050

using namespace std;

char s[MAXN];
char s2[2*MAXN];

void build()
{
    for (int i = 0, t = 2*strlen(s)+1; i < t; i++)
        if (i & 1)
            s2[i] = s[i>>1];
        else
            s2[i] = '*';
}

int p[2*MAXN];
long long sol;

void solve()
{
    int r = 0, st, dr, c;
    for (int i = 1, t = strlen(s2); i < t; i++) {
        if (i > r) {
            st = i-1;
            dr = i+1;
        }
        else {
            int mir = (c<<1)-i;
            if (i+p[mir] < r) {
                p[i] = p[mir];
                st = -1;
            }
            else {
                p[i] = p[mir];
                st = i - p[i]-1;
                dr = i + p[i]+1;
            }
        }
        while (st >= 0 && dr < t && s2[st] == s2[dr])
            st--, dr++, p[i]++;
        if (i+p[i] > r) {
            r = i+p[i];
            c = i;
        }
        sol += (p[i]+1)>>1;
    }
}

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

    gets(s);
    build();
    solve();
    printf("%lld", sol);

    return 0;
}