Cod sursa(job #1514233)

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

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

using namespace std;

int n, rgt, i, pal, ok, sol;
int 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], 1);
        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], 0);
        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("%d", sol);

    return 0;
}