Cod sursa(job #1514237)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 30 octombrie 2015 21:11:21
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013

using namespace std;

typedef long long LL;

LL n, rgt, i, pal, ok, sol;
LL l[1000005];
char sir[1000005];

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

    gets(sir + 1);
    n = strlen(sir + 1);

    rgt = pal = 0;
    for(i = 1; i <= n; i++)
    {
        if(rgt >= i)
            l[i] = min(l[pal * 2 - i], rgt - i + 1);

        l[i] = max(l[i], 1LL);
        while(sir[ i + l[i] ] == sir[ i - l[i] ] && i + l[i] <= n && i - l[i] >= 1)
            l[i]++;

        sol += l[i];

        if(i + l[i] - 1 > rgt)
        {
            rgt = i + l[i] - 1;
            pal = i;
        }
    }

    rgt = pal = 0;
    l[1] = 0;
    for(i = 2; i <= n; i++)
    {
        l[i] = 0;
        if(rgt >= i)
            l[i] = min(l[pal * 2 - i], rgt - i + 1);

        l[i] = max(l[i], 0LL);
        while(sir[ i + l[i] ] == sir[ i - l[i] - 1 ] && i + l[i] <= n && i - l[i] - 1 >= 1)
            l[i]++;

        sol += l[i];
        if(i + l[i] - 1 > rgt)
        {
            rgt = i + l[i] - 1;
            pal = i;
        }
    }

    printf("%lld", sol);

    return 0;
}