Cod sursa(job #1212755)

Utilizator nicolaegutaNicolae Guta nicolaeguta Data 25 iulie 2014 19:23:28
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <cstring>
#define Nmax 2000005

using namespace std;

char a[Nmax],b[Nmax];
int N,Z[Nmax];
long long sol;

inline void Manacher()
{
    int L,M=0,R=0,t,i;
    Z[1]=0;
    for(i=2;i<=N;++i)
        if(i>R)
        {
            M=i;
            for(R=M+1;R<=N && a[R]==a[2*M-R];++R);
            --R;
            Z[i]=R-M;
        }
        else
        {
            t=2*M-i; L=2*M-R;
            if(Z[t]<t-L)
                Z[i]=Z[t];
            else
            {
                M=i;
                for(++R;R<=N && a[R]==a[2*i-R];++R);
                --R;
                Z[i]=R-M;
            }
        }
}

int main()
{
    int i;
    freopen ("pscpld.in","r",stdin);
    freopen ("pscpld.out","w",stdout);
    scanf("%s", (a+1));
    N=strlen(a+1);
    Manacher();
    for(i=1;i<=N;++i)
        sol+=Z[i];
    sol+=N;
    for(i=1;i<=N;++i)
    {
        b[2*i]=a[i]; b[2*i-1]='*';
    }
    b[2*N+1]='*';
    N=2*N+1;
    for(i=1;i<=N;++i)
        a[i]=b[i];
    Manacher();
    for(i=3;i<=N;i+=2)
        sol+=(Z[i]/2);
    printf("%lld\n", sol);
    return 0;
}