Cod sursa(job #1527482)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 18 noiembrie 2015 10:00:57
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define in "pscpld.in"
#define out "pscpld.out"
#define NMAX 2000007
#define LL long long

using namespace std;

int sol[NMAX], n, mij, edge;
char s[NMAX];
LL rez;

inline void convert()
{
    n=strlen(s+1);
    for(int i=n;i;i--)
    {
        s[(i<<1)] = s[i];
        s[(i<<1)-1] = '$';
    }
    n = (n<<1)|1;
    s[n] = '$';
    mij = edge = 1;
}
inline void manacher()
{
    for(int i=2; i<=n; ++i)
    {
        if(i <= edge) sol[i] = min(sol[(mij<<1) - i], edge - i);
        while(1 <= i-sol[i]-1 && i+sol[i]+1 <= n && s[i-sol[i]-1] == s[i+sol[i]+1]) sol[i]++;
        if(i+sol[i] > edge)
        {
            edge=i+sol[i];
            mij=i;
        }
    }
}
inline void afisare()
{
    for(int i=1; i<= n; ++i)
        if(i&1) rez += ((sol[i]+1)>>1);
        else rez += ((sol[i]+2)>>1);
    printf("%lld",rez);
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%s",s+1);
    convert();
    manacher();
    afisare();
    return 0;
}